This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

This is the first time I am taking dynamic programming seriously. The below are the lists of questions I have done so far:

https://leetcode.com/problems/min-cost-climbing-stairs/
https://leetcode.com/problems/fibonacci-number
https://leetcode.com/problems/n-th-tribonacci-number/
https://leetcode.com/problems/pascals-triangle-ii/
https://leetcode.com/problems/get-maximum-in-generated-array/
This youtube video helped a bit:
https://www.youtube.com/watch?v=xOlhR_2QCXY

Dynamic programming has always been scary to me, so I held off for years and now forced to take it seriously as I should be interviewing soon.

The first I noticed that dynamic programming is progressing linearly forward in nature. This is important to keep in mind as the youtube video had a little confusing bit where he talked about dynamic programming starts with a recursive function. Recursive function does not progress linearly like a for loop is. However, dynamic programming has to be linear in some way, because it is the records of computed values that is where the magic lies.

Therefore notice that the knapsack problem is not really the best first dynamic programming question, but it is definitely one that is complicated enough to be worthwhile of discussion. I really think he should first mentioned the easier questions then throw in knapsack for the added complexity of recursion.

I started with min-cost-climbing-stairs, but couldn't solve it due to thinking I need to start first with recursion.

fibonacci-number is a much better start, here is my code:

const memo = [0,1];

var fib = function(n) {
    if(memo.hasOwnProperty(n)) {
        return memo[n];
    }

    n-= memo.length-1;

    while (n--) {
        memo.push(memo[memo.length-1] + memo[memo.length-2]);
    };

    return memo[memo.length-1];
};

the memo[] is outside of the function so it becomes global during the submission for all the test cases.
The pattern in this code will be essential for subsequent problems:
1.) memo[] initialization as well as returning memoized value if exists.

2.) n-= memo.length-1; so that we are only adding to the memo[] as needed

3.) while loop to add in for numbers

4.) returning the latest value

n-th-tribonacci-number is literally the same problem except with one more term for the addition, not worth further explanation.

pascals-triangle-ii is similar enough as well.

get-maximum-in-generated-array is different enough, below is the code:

const maxes = [0, 1];
const memo  = [0, 1];
var getMaximumGenerated = function(n) {
    if(maxes.hasOwnProperty(n)) { 
        return maxes[n]; 
    }

    n -= (memo.length-1);
    let len;
    while(n--) {
        len = memo.length;
        if(len % 2 ===0) {
            memo[len] = memo[len/2];
        } else {
            memo[len] = memo[(len-1)/2] + memo[(len-1)/2+1];
        }

        maxes.push(
            Math.max(
                maxes[maxes.length-1], 
                memo[len]
            )
        );
    }

    return maxes[maxes.length-1];
};

Note that a slight improvement is that I added another memoization for the maximum value for each subarray as each memo value is added. Surprisingly the memory usage is still lower than 89% of all submissions.

I'll probably continue on this track for several days to come until I am doing medium dynamic programming questions relatively well.

Let me know anything on your mind after reading through this, THANKS!