Press "Enter" to skip to content

Posts tagged as “Dynamic Programing”

LeetCode 279. Perfect Squares (javascript)

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

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, 149, 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];
};

LeetCode 198. House Robber (javascript)

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];
};

LeetCode 85. Maximal Rectangle (javascript)

Given a rows x cols binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing only 1‘s and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = []
Output: 0

Example 3:

Input: matrix = [["0"]]
Output: 0

Example 4:

Input: matrix = [["1"]]
Output: 1

Example 5:

Input: matrix = [["0","0"]]
Output: 0

Constraints:

  • rows == matrix.length
  • cols == matrix[i].length
  • 0 <= row, cols <= 200
  • matrix[i][j] is '0' or '1'.

Idea:

Dynamic Programing

  • Time complexity: O(mn)
  • Space complexity: O(mn)
dp[i][j] := max length of all 1s ends with col j at row i.
dp[i][j] = 0 if matrix[i][j] == "0"
dp[i][j] = dp[i][j-1] + 1 if matrix[i][j] == "1"

Then loop through matrix
Min Width(has "1"):= Math.min(width, dp[curRow][j]);
Min Height(has "1"):= curRow - i + 1;
MaxArea = Min Width * Min Height

Solution:

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function(matrix) {    
    let row = matrix.length;
    if (row === 0) return 0;
    let col = matrix[0].length;
    
    // dp[i][j] := max length of all 1s ends with col j at row i.
    // dp[i][j] = 0 if matrix[i][j] == "0"
    // dp[i][j] = dp[i][j-1] + 1 if matrix[i][j] == "1"
    let dp = Array.from(new Array(row), () => new Array(col));
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (matrix[i][j] === "1") {
                dp[i][j] = j === 0 ? 1 : dp[i][j - 1] + 1;
            } else {
                dp[i][j] = 0;
            }
        }
    }
    
    let maxArea = 0;
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            let width = Infinity;
            for (let curRow = i; curRow < row; curRow++) {
                width = Math.min(width, dp[curRow][j]);
                if (width === 0) break;
                let height = curRow - i + 1;
                maxArea = Math.max(maxArea, width * height);
            }
        }
    }
    return maxArea;
};

LeetCode 1277. Count Square Submatrices with All Ones (javascript)

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;
};

LeetCode 1143. Longest Common Subsequence (javascript)

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

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".

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];
}

LeetCode 300. Longest Increasing Subsequence (javascript)

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

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);
};

118. Pascal’s Triangle (javascript)

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

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

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

  • 1 <= numRows <= 30

Solution:

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
    let res = [[1]];
    
    while(numRows > 1) {
        let previous = res[res.length - 1];
        // The first row element is always 1.
        let cur = [1];
        for (let i = 1; i < previous.length; i++) {
            // generate: sum of the elements above-and-to-the-left and above-and-to-the-right.
            cur.push(previous[i - 1] + previous[i]);
        }
        // The last row element is always 1.
        cur.push(1);
        res.push(cur.concat());
        numRows--;
    }
    return res;
};

LeetCode 70. Climbing Stairs (javascript)

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

  • 1 <= n <= 45

Idea:

Dynamic programing

dp[i] represents how many distinct ways climb i stairs to the top
dp[1] = 1;
dp[2] = 2;
dp[3] = dp[2] + d[1];
dp[4] = dp[3] + d[2];
...
dp[i] = dp[i - 1] + dp[i - 2];

Solution:

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let dp = Array.from(new Array(n + 1));
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};

LeetCode 64. Minimum Path Sum (javascript)

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];
}

LeetCode 62. Unique Paths (javascript)

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];
}