LeetCode dynamic programming topic Javascript language detailed analysis 1.0
What is Dynamic Planning
Dynamic programming, or DP for short, is most effective when a problem has many overlapping subproblems. So each state in dynamic programming must be derived from the previous state, which distinguishes it from greed, which has no state derivation, but chooses the optimal one directly from the local.
Fibonacci Number
509. Fibonacci Number
each number is the sum of the two preceding ones, starting from 0 and 1. That is
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).
var fib = function(n) {
let dp = [0, 1]
for(let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n]
};
Climbing Stairs
70. Climbing Stairs
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?
thinking
There is one way to climb to the first staircase, and two ways to climb to the second staircase.
Then the first stairway is two steps further to the third stairway, and the second stairway is one step further to the third stairway.
So the state of the stairs to the third level can be derived from the second level stairs and the first level stairs state, that is, a certain level stairs is equal to the sum of the first two stairs state, then we can think of dynamic programming.
var climbStairs = function (n) {
// dp[i] is the number of ways to climb the i-th stair to the top of the building.
let dp = [1, 2]
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n - 1]
}
Space Complexity Optimization
var climbStairs = function (n) {
let a = 0,
b = 1,
c = 0
for (let i = 1; i <= n; i++) {
c = a + b
a = b
b = c
}
return c
}
Min Cost Climbing Stairs
746. Min Cost Climbing Stairs
You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index 0, or the step with index 1. Return the minimum cost to reach the top of the floor.
var minCostClimbingStairs = function (cost) {
let dp = [cost[0], cost[1]]
let len = cost.length
for (let i = 2; i < len; i++) {
//cost[i]:Whenever you climb a certain ladder you have to spend the stamina value corresponding to this ladder,
Select the value that costs less in the first two steps plus cost[i]
dp[i] = cost[i] + Math.min(dp[i - 2], dp[i - 1]);
}
return Math.min(dp[len - 1], dp[len - 2])
// Note that the last step can be interpreted as no cost, so take the least value of the penultimate step and the second step
}
Space Complexity Optimization
var minCostClimbingStairs = function (cost) {
let dp1 = cost[0]
let dp2 = cost[1]
for (let i = 2; i < cost.length; i++) {
let res = Math.min(dp2, dp1) + cost[i]
dp1 = dp2
dp2 = res
}
return Math.min(dp2, dp1)
}
Unique Paths
62. Unique Paths
A robot is located in the upper left corner of an m x n grid (the start point is marked "Start" in the figure below).
The robot can only move down or to the right one step at a time. The robot tries to reach the lower right corner of the grid (marked as "Finish" in the figure below).
Ask how many different paths there are in total.
thinking
Initialization of the dp array How to initialize it, first of all dp[i][0] must all be 1, because there is only one path from the position of (0, 0) to (i, 0), then dp[0][j] is also the same.
for (let i = 0; i < m; i++) {
arr[i][0] = 1
}
for (let i = 0; i < n; i++) {
arr[0][i] = 1
}
Determine the recurrence formula Want to require dp[i][j], there are only two directions to derive it, dp[i - 1][j] and dp[i][j - 1]: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
Full Code
var uniquePaths = function (m, n) {
let arr = new Array(m).fill(0).map(() => new Array(n).fill(0))
for (let i = 0; i < m; i++) {
arr[i][0] = 1
}
for (let i = 0; i < n; i++) {
arr[0][i] = 1
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
arr[i][j] = arr[i - 1][j] + arr[i][j - 1]
}
}
return arr[m - 1][n - 1]
}
Dimensionality reduction using rolling arrays
var uniquePaths = function (m, n) {
let dp = new Array(n).fill(0)
for (let i = 0; i < n; i++) dp[i] = 1
for (let j = 1; j < m; j++) {
for (let i = 1; i < n; i++) {
dp[i] += dp[i - 1]
}
}
return dp[n - 1]
}
Unique Paths II
You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m-1][n-1]). The robot can only move either down or right at any point in time.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
thinking
The recursive formula for this problem is the same as the previous one, except that there are more obstacles.Because there is only one path from the position of (0, 0) to (i, 0), dp[i][0] must be 1, and dp[0][j] is the same.
However, if (i, 0) has a barrier on this edge, after the barrier (including the barrier) are positions that cannot be walked, so the dp[i][0] after the barrier should still have the initial value of 0.So the initialization code for this question is
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
Note the termination condition of the for loop in the code, once the obstacleGrid[i][0] == 1, stop the dp[i][0] assignment 1 operation, dp[0][j] the same
Full Code
var uniquePathsWithObstacles = function (obstacleGrid) {
if (obstacleGrid[0][0] == 1) return 0
let m = obstacleGrid.length
let n = obstacleGrid[0].length
let arr = new Array(m).fill(0).map(() => new Array(n).fill(0))
for (let i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
//Note the termination condition of the for loop in the code, once the obstacleGrid[i][0] == 1, stop the dp[i][0] assignment 1 operation
//Because the first row or column encounters an obstacle, the path after the first row or column cannot be reached.
arr[i][0] = 1
}
for (let i = 0; i < n && obstacleGrid[0][i] == 0; i++) {
arr[0][i] = 1
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
continue
}
arr[i][j] = arr[i - 1][j] + arr[i][j - 1]
}
}
return arr[m - 1][n - 1]
}
Integer Break
Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.
Return the maximum product you can get.
thinking
Traversing from 1 to j, then there are two channels to get dp[i].
One is j * (i - j) multiplied directly.
One is j * dp[i - j], which is equivalent to splitting (i - j)
It can also be understood that j * (i - j) is simply splitting an integer into two numbers and multiplying them together, while j * dp[i - j] is splitting into two and more numbers and multiplying them together.
var integerBreak = function (n) {
let dp = new Array(n + 1).fill(0);
//To get the subscript n length has to be n+1
dp[2] = 1;dp[1]=1
for (let i = 3; i <= n; i++) {
for (let j = 1; j <=i-j; j++) {
//Here j cannot be equal to 0, because there is (i-j)*j
//ivide n into j and i-j; so the range of j is 1 to i-j
let m = dp[i - j] * j;
/*Iterate through all j, i-j can choose to split or not, not split is i-j, split is dp[i - j]*j,
because dp is the process of splitting one by one in front*/
let n = (i - j) * j;
//The positive integer n becomes here the positive integer i. The pointer j is used to divide i into j and i - j (i=i-j+j)
dp[i] = Math.max(dp[i], m, n);
}
}
return dp[n];
};
Unique Binary Search Trees
96. Unique Binary Search Trees
Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.
thinking
There is one tree when n is 1 and two trees when n is 2 dp[3], is the number of search trees with element 1 as the head node + the number of search trees with element 2 as the head node + the number of search trees with element 3 as the head node
Element 1 is the number of head node search trees = the number of search trees with 2 elements in the right subtree * the number of search trees with 0 elements in the left subtree
Element 2 is the number of head node search trees = the number of search trees with 1 element in the right subtree * the number of search trees with 1 element in the left subtree
Element 3 is the number of head node search trees = the number of search trees with 0 elements in the right subtree * the number of search trees with 2 elements in the left subtree
So dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
var numTrees = function (n) {
let dp = new Array(n + 1).fill(0);
//Length n+1 to get the subscript n
dp[0] = 1; dp[1] = 1;
/Note that must be initialized dp[0]=1,
because the later loop useful to dp[j], j = 0 that dp[0], if not initialized to 1 multiply the results will become 0*/
for (let i = 2; i <= n; i++) {
for (let j = 0; j <= i - 1; j++) {
//Build BST with i nodes, remove the root node, leaving i-1 nodes to build the left and right subtree, the left subtree is assigned 0, then the right subtree is assigned to i-1 ...... and so on.
// that is, the left subtree from having 0 to n-1, the right subtree correspondingly assigned to n-1 to 0 (so j = 0; j <= i-1 that j <= n-1
dp[i] += dp[j] * dp[i - j - 1];
}
}
return dp[n];
};
