# Longest Increasing Subsequence - Dynamic Programming / Dynamic number of subproblems

Hello! It looks like there some typo in your markdown content for the examples. I see a part of markdown table syntax there :P.

Hi, we updated the example!

Hi, Isn’t it more of two pointer than the Dynamic programming?

Please fix typo in this sentence → “If a number before current number is smaller than current number nums[j] < nums[i], then we can update dp[i] to be max(d[i], dp[j] + 1). dp[j] + 1 because the new subsequence is whatever the subsequence ending in j plus the current element.”

Correct sentence would be → “If a number before current number is smaller than current number nums[j] < nums[i], then we can update dp[i] to be max(dp[i], dp[j] + 1). dp[j] + 1 because the new subsequence is whatever the subsequence ending in j plus the current element.”

I would be great if we can provide both the top-down and the bottom-up solutions for these DP problems. Looking at 2 different solution approach helps in visualization of the problem better:

My top-down approach solution:

``````    public static int longestSubLen(List<Integer> nums) {
if (nums.size() == 0) {
return 0;
}

int[] dp = new int[nums.size()];

for (int i=0; i<nums.size(); i++) {
compute(i, nums, dp);
}

int max = 1;
for (int i=0; i<dp.length; i++) {
max = Math.max(max, dp[i]);
}
return max;
}

private static void compute(int index, List<Integer> nums, int[] dp) {
if (dp[index] != 0) {
return;
}

dp[index] = 1;
for (int j = index+1; j<nums.size(); j++) {
if (nums.get(index) < nums.get(j)) {
compute(j, nums, dp);
dp[index] = Math.max(dp[index], 1 + dp[j]);
}
}
}`````````

@abhi
Couldn’t agree more.
By the way, nicely done.

Shouldn’t the best variable be initialized to 1 instead 0? This is because if the largest increasing sequence is of size 1 (which it is always at least 1) we will be returning best = 0 which is incorrect.