Dynamic Programming practices: Leetcode problems in JavaScript

Dynamic programming is one important thinking in computer science. It’s always applied to recursion problems due to the great performance in reducing the running time by creating extra space to save the previous results. In this post, I’ll list several classical dynamic programming problems along with their solutions in JavaScript.

Fibonacci Number

Fibonacci Number - LeetCode

There are several solutions to this problem. We’re familiar with recursion one: we recursively calculate the fib(n-1) and fib(n-2) until we meet the edge case. However, recursively calculate a Fibonacci number will result in O(2^N) running time. By applying dynamic programming, we can reduce it to O(N) by creating an array to memorize the previous result.

For example, if the given N is 8. We’ll create an array to store the fib number in range[2, N] .

original dp: [0, 1]
when i = 2, fib(2) = dp[2–1] + dp[2–2], dp = [0,1,1];
when i = 3, fib(3) = dp[3–1] + dp[3–2], dp = [0,1,1,2];
when i = 4, fib(4) = dp[4–1] + dp[4–2], dp = [0,1,1,2,3];
when i = 5, fib(5) = dp[5–1] + dp[5–2], dp = [0,1,1,2,3,5];
when i = 6, fib(6) = dp[6–1] + dp[6–2], dp = [0,1,1,2,3,5,8];
when i = 7, fib(7) = dp[7–1] + dp[7–2], dp = [[0,1,1,2,3,5,8,13];
when i = 8, fib(8) = dp[8–1] + dp[8–2], dp = [[0,1,1,2,3,5,8,13,21];
fib(8) = 21

The solution in JS:

var fib = function(N) {
    if (N === 0) {
        return 0
    } else if (N == 1) {
        return 1
    }
    var dp = [0, 1]
    for (var i = 2; i <= N; i++) {
        var number = dp[i - 1] + dp[i - 2]
        dp.push(number)
    }
    return dp[dp.length - 1]
};

Longest Increasing Subsequence

Longest Increasing Subsequence - LeetCode

The dynamic programming algorithm is frequently used in finding the maximum or minimum properties of a given array. For this problem, we could have a dp array to memorize by dp[i], the longest increasing sequence length.

array = [10,9,2,5,3,7,101,18]
dp = [1,1,1,2,2,3,4,4]
longest increasing subsequence = 4

JS code:

var lengthOfLIS = function(nums) {
    if (!nums || nums.length === 0) {
        return 0
    }
    
    if (nums.length === 1) {
        return 1
    }
    
    var dp = new Array(nums.length).fill(0)
    var max = 0
    
    for (var i = 0; i < nums.length; i++) {
        dp[i] = 1
        for (var j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1
            }
        }
        max = Math.max(max, dp[i])
    }
    console.log(dp)
    return max
};

Minimum Path Sum

Minimum Path Sum - LeetCode

Similar to the array, the matrix can also store the previous results. For example, we can have matrix[i][j] store the minimum path sum at the current position.

matrix = [
          [1,3,1],
          [1,5,1],
          [4,2,1]]
    dp = [
          [1,4,5],
          [2,7,6],
          [6,8,7]]    minimum path = 7

JS code:

var minPathSum = function(grid) {
    if (!grid || grid.length === 0 || grid[0].length === 0) {
        return 0;
    }
    var m = grid.length
    var n = grid[0].length
    for (var i = 0; i < grid.length; i++) {
        for (var j = 0; j < grid[i].length; j++) {
            if (i === 0 && j === 0) {
                grid[i][j] *= 1
            } else if (i === 0 && j !== 0) {
                grid[i][j] += grid[i][j - 1]
            } else if(i !== 0 && j === 0) {
                grid[i][j] += grid[i - 1][j]
            } else {
                grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j])
            }
        }
    }
    return grid[m - 1][n - 1]
};