Estoy trabajando en https://leetcode.com/problems/longest-increasing-subsequence
Para caso de prueba
input: [5, 4, 19, 5, 7, 12]; output: 4Sin el caché, puedo generar 4 correctamente.
var lengthOfLIS = function (ns) { if (ns.length === 1) return 1; const prev_i = -1; const curr_i = 0; const res = 0; return recur(ns, prev_i, curr_i, res); }; // good var recur = function (ns, prev_i, curr_i, res) { // if (curr_i >= ns.length) { return res; } // take let out_1 = 0; if (prev_i === -1) { out_1 = recur(ns, curr_i, curr_i + 1, res + 1); } else if (ns[curr_i] > ns[prev_i]) { out_1 = recur(ns, curr_i, curr_i + 1, res + 1); } else if (ns[curr_i] <= ns[prev_i]) { out_1 = res; } // !take let out_2 = 0; out_2 = recur(ns, prev_i, curr_i + 1, res); const max = Math.max(out_1, out_2); return max; };Cuando le agrego caché, mi salida es 3.
var recur = function (dp, ns, prev_i, curr_i, res) { // if (curr_i >= ns.length) { return res; } if (prev_i !== -1 && dp[prev_i + 1][curr_i + 1] !== undefined) { return dp[prev_i + 1][curr_i + 1]; } // take let out_1 = 0; if (prev_i === -1) { out_1 = recur(dp, ns, curr_i, curr_i + 1, res + 1); } else if (ns[curr_i] > ns[prev_i]) { out_1 = recur(dp, ns, curr_i, curr_i + 1, res + 1); } else if (ns[curr_i] <= ns[prev_i]) { out_1 = res; } // !take let out_2 = 0; out_2 = recur(dp, ns, prev_i, curr_i + 1, res); const max = Math.max(out_1, out_2); dp[prev_i + 1][curr_i + 1] = max; return max; }; var lengthOfLIS = function (ns) { if (ns.length === 1) return 1; const dp = Array(ns.length + 1) .fill(undefined) .map((_, i) => { return Array(ns.length + 1).fill(undefined); }); const prev_i = -1; const curr_i = 0; const res = 0; return recur(dp, ns, prev_i, curr_i, res); };¿Alguien podría señalar algún error que cometí? Estoy tratando de usar el depurador para ver qué está sucediendo.
Puede depurar este tipo de problema comparando el resultado almacenado en caché con el resultado no almacenado en caché y registrando las diferencias.
El problema es que el resultado de esta función depende de los valores de prev_i, curr_i y res. Sin embargo, su caché solo depende de los valores de prev_i y curr_i, por lo que no tiene suficiente información para predecir el resultado correcto.