I am working on https://leetcode.com/problems/longest-increasing-subsequence
For test case
input: [5, 4, 19, 5, 7, 12]; output: 4
Without the cache, I am able to output 4 correctly.
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;
};
When I adding cache to it, my output is 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);
};
Could someone point out any mistake I made? I am trying to use debugger to see what is happening.