# Posts tagged as “Dynamic Programing”

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

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

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

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

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

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