Posts published in “Dynamic Programming”

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints:

• 1 <= n <= 104

Idea: (Dynamic Programing)

• Time complexity: O(n * sqrt(n))
• Space complexity: O(n)

dp[i] := return the least number of perfect square numbers that sum to i.
dp[0] = 0
dp[i] = min{dp[i – j * j] + 1} and 1 <= j * j <= i ex:[1, 4, 6, 9…]
// For example:
dp[5] = min{
dp[5 – 2*2] + 1 = dp[1] + 1 = (dp[1 – 1*1] + 1) + 1 = dp[0] + 1 + 1 = 2,
dp[5 – 1*1] + 1 = dp[4] + 1 = (dp[4 – 1*1] + 1) + 1 = dp[3] + 2 = 
dp[3 – 1*1] + 1 + 2 = dp[2 - 1*1] + 1 + 3 = dp[1 - 1*1] + 1 + 4 = 
dp[0] + 5 = 5
 };
so dp[5] = 2

Solution:

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    // Important: n + 1 length because we use dp[0]
    let dp = new Array(n + 1).fill(Number.MAX_VALUE);
    dp[0] = 0;
    for (let i = 1; i <= n; i++)
        for(let j = 1; j * j <= i; j++)
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    
    return dp[n];
};

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

Idea:

Dynamic Programing

Try to look for a pattern, see comments in the code.

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    // one house
    if (nums.length === 1) return nums[0];
    
    // dp[i] = max money can be taken after visited i houses
    let dp = new Array(nums.length);
    dp[1] = nums[0];
    dp[2] = Math.max(nums[0], nums[1]);
    // two houses
    if (nums.length === 2) return dp[2];
    
    // more houses - try to look for a pattern
    // dp[3] = Math.max(dp[2], dp[1] + nums[2]);
    // dp[4] = Math.max(dp[3], dp[2] + nums[3]);
    // ...
    for (let i = 3; i <= nums.length; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
    }
    return dp[nums.length];
};

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

Constraints:

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

Idea:

Dynamic Programing

• dp[i][j] := edge of largest square with bottom right corner at (i, j)
• base case:
  • dp[0][0], dp[i][0], dp[0][j] = 1 if martix[i][j] = 1
• The current unit can form the largest square matrix with the left, upper and upper left units. For example, a unit can form a matrix with a side length of 3 with the left, top, and top left units. That can also form a matrix with a side length of 2 and a side length of 1. So:
  • dp[i][j] = min(dp[i – 1][j], dp[i – 1][j – 1], dp[i][j – 1])+1 if matrix[i][j] == 1 else 0
• Return answer:
  • ans = sum of all dp[i][j]

Solution:

/**
 * @param {number[][]} matrix
 * @return {number}
 */
var countSquares = function(matrix) {
    let row = matrix.length;
    let col = matrix[0].length;
    let dp = Array.from(new Array(row), () => new Array(col));
    let sum = 0;
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            // Basic cases: 
            // dp[0][0], dp[i][0], dp[0][j] cases => has 1, form a square
            dp[i][j] = matrix[i][j];
            
            if (i && j && dp[i][j]) // Why? See Above
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1;

            sum += dp[i][j];
        }   
    }
    return sum;
};

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

Idea:

Dynamic Programing

Use dp[i][j] to represent the length of longest common sub-sequence of text1[0:i-1] and text2[0:j-1]
dp[i][j] = dp[i – 1][j – 1] + 1 if text1[i – 1] == text2[j – 1] else max(dp[i][j – 1], dp[i – 1][j])

Solution:

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    // Use dp[i][j] to represent the length of longest common sub-sequence of text1[0:i-1] and text2[0:j-1]
    // dp[i][j] = dp[i – 1][j – 1] + 1 if text1[i – 1] == text2[j – 1] else max(dp[i][j – 1], dp[i – 1][j])
    let dp = Array.from(new Array(text1.length + 1), () => new Array(text2.length + 1));
    
    // final result dp[i + 1][j + 1] contains length of LCS  
    // for text1[0..i] and text2[0..j], so use <=
    for (let i = 0; i <= text1.length; i++) {
        for (let j = 0; j <= text2.length; j++) {
            // base case:
            if (i === 0 || j === 0) 
                dp[i][j] = 0;
            else if (text1[i - 1] === text2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    // dp[text1.length][text2.length] contains length of LCS  
    // for text1[0..text1.length-1] and text2[0..text2.length-1]
    return dp[text1.length][text2.length];
}

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

Idea:

dp[i] represents the length of the longest increasing subsequence of nums[0...i]
dp[0] = 1
dp[i] = max(dp[j]'s) + 1 if j < i when nums[i] > nums[j]
result: find the max of all dp[i]'s

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let dp = new Array(nums.length);
    dp[0] = 1;
    for (let i = 0; i < nums.length; i++) {
        // local max
        let max = 0;
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                max = Math.max(dp[j], max);
            }
        }
        dp[i] = max + 1;
    }
    // result: find the max of all dp[i]'s
    return Math.max(...dp);
};

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

Idea:

Dynamic Programing

save space: we just use the original grid to calcuate the min path sum
grid[i][j] represent the min path sum of i x j grid
grid[i][j] = get the min of previous grid(top/left) + current val

Solution:

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    // save space: we just use the original grid to calcuate the min path sum
    // grid[i][j] = min path sum of i x j grid
    let m = grid.length;
    let n = grid[0].length;
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // grid[0][0] itself contains the min path sum
            if (i === 0 && j === 0) continue;
            // first row: grid[i][j] = previous grid(left) + current val
            if (i === 0) grid[i][j] += grid[i][j - 1];
            // first column: grid[i][j] = previous grid(top) + current val
            else if (j === 0) grid[i][j] += grid[i - 1][j];
            // grid[i][j] = get the min of previous grid(top/left) + current val
            else grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);
        }
    }
    return grid[m - 1][n - 1];
}

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Example 3:

Input: m = 7, n = 3
Output: 28

Example 4:

Input: m = 3, n = 3
Output: 6

Constraints:

• 1 <= m, n <= 100
• It’s guaranteed that the answer will be less than or equal to 2 * 109.

Idea:

Dynamic Programing

dp[m][n] = unique paths of m x n grid
// base case:
dp[1][1] = 1; 
// dp[i][j] = top(unique paths) + left(unique paths)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

Solution:

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    // one row or one column dp[i][1] = dp[1][j] = 1; Let's fill them all 1
    let dp = Array.from(new Array(m), () => new Array(n).fill(1));
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // dp[i][j] = top(unique paths) + left(unique paths)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}