Time: 2021.9.26-2021.9.30
Overview of Dynamic programming
Dynamic programming is a branch of operations programming. It is a mathematical method to solve the optimization of decision process. It is the optimization principle proposed by American mathematician R.E.Bellman et al in the early 1950s. It uses the relationship between each stage to solve one by one and finally obtains the global optimal solution. When designing dynamic programming algorithm, the key elements such as original problem and sub-problem, dynamic programming state, boundary state junction value and state transition equation should be confirmed.
Principle of dynamic programming
(Take subject 1 as an example)
1. Confirm the original problem and sub-problem: the original problem is to find the number of all steps of n steps, the sub-problem is to find 1 step, 2 step,… N minus one steps.
2. Confirm state: In this case, the dynamic planning state is single. The ith state is the number of all moves of step I.
3. Confirm the value of boundary state: the boundary state is the way of step 1 and step 2. There is one way for step 1 and two ways for step 2, that is, DP [1]= 1 and DP [2]= 2.
4. Determine the state transition equation: transfer the value of the i-th state to the value of the i-1st state and the i-2nd state, dynamically programming the transition equation, dp[I] = DP [i-1] + DP [i-2]; (I > = 3).
1. LeetCode70 climbs stairs
D [0..n], dp[I], how many ways to get to order I, initialize array element 0.
2. Set to reach the first step, there is one way; There are two ways to get to step two.
3. Use I cycle recursion from the 3rd order to the NTH order result: the number of ways to reach the I order = the number of ways to reach the I-1 order + the number of ways to reach the I-2 order
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 2];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
returndp[n]; }}Copy the code2. LeetCode198 Raids
1. Confirm the original problem and sub-problem: the original problem is to find the optimal solution of N rooms, the sub-problem is to find the first 1 room, the first 2 rooms,.. The best solution for the first n minus 1 rooms.
2. Confirm state: The ith state is the maximum treasure that the previous I room can obtain (optimal solution).
3. Confirm the value of boundary state: the optimal solution of the first room, treasure of the first room; The optimal solution of the first two rooms, the larger treasure in the first and second rooms.
4. Determine the state transition equation :a. Select the optimal solution of the first room: the i-th room + the first i-2 rooms.
B. Do not select the i-th room: the optimal solution of the former i-1 room.
Dynamic programming transfer equation: DP [I] = Max (DP [i-1], DP [i-2] + NUMS [I]); (I > = = 3).
class Solution {
public int rob(int[] nums) {
if (nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
// let the optimal solution of room I be dp[I]
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
}
return dp[nums.length -1]; }}Copy the code3. The maximum suborder sum of LeetCode53
The maximal subsegment sum of an array of n numbers is the maximal subsegment sum of an array of n numbers. The maximal subsegment sum of n numbers is the maximal subsegment sum of an array of n numbers. I… The sum of the largest fields at the end of the NTH digit, and then find the largest of the n results, that is, the result.
Dynamic programming algorithm: the ith state (DP [I]) is the largest sum of subsegments ending in the ith number (optimal solution). If dp[i-1] > 0:dp[I] = dp[i-1] + nums[I]; Dp [I] = nums[I]; Boundary values: the largest field ending in the first digit and dp[0] = nums[0].
class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(nums[i], dp[i] = dp[i -1] + nums[i]);
if(dp[i] > max) { max = dp[i]; }}returnmax; }}Copy the code4. Change LeetCode322
Coins =[1,2,5, 7,10] Amount: 14; Dp [I], represents the optimal solution of the amount (i.e., the minimum number of sheets used); The optimal solution for storing amounts 1 to 14 in array dp[] (the least amount of banknotes used). When calculating dp[I], dp[0], DP [1], DP [2],.. Dp [i-1] is given. The amount can be: i-1 and Coins [0] (1); Amount I-2 is combined with Coins [1] (2); Amount I-5 is combined with Coins [2] (5); Amount I-7 is combined with Coins [3] (7); Amount I-10 is combined with Coins [4] (10); That is, state I can be transferred from state I-1, I-2, I-5, I-7, i-10, so dp[I] = min(DP [i-1], DP [i-2], DP [i-5], DP [i-7], DP [i-10])+ 1.
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
// Initialize the dp array, the optimal solution for all initial amounts is -1 (unreachable)
Arrays.fill(dp, -1);
// The optimal solution to amount 0 is 0
dp[0] = 0;
// Obtain all the optimal solutions between 1 and I, thus deriving the optimal solution for I
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (i - coins[j] >= 0&& dp[i - coins[j]] ! = -1) {
if(dp[i] == -1 || dp[i] > dp[i - coins[j]]+1){
dp[i] = dp[i - coins[j]] + 1; }}}}returndp[amount]; }}Copy the code5. LeetCode120 triangle minimum path sum
1. Set a two-dimensional array with the optimal value of triangle dp[] [] and initialize the array element to 0. Dp [I] [j] represents the optimal solution to row I and column J of the triangle when recursively from bottom up.
2. Dynamically plan the triangle from the bottom to the top. A. Dynamic programming boundary conditions: the optimal value on the bottom surface is the last layer of the digital triangle. B. Recursively from the penultimate layer to the first layer by using cycle I. For each column of each layer, dynamic programming recursion is carried out: The optimal solution for row I and column J is dp[I] [j], Can be reached (I, j) two positions of the optimal solution of dp [j], [I + 1] dp [I + 1] : [m + 1] dp [I] [j] = min (dp [j], [I + 1] dp + 1] [I [j + 1)) + triangle [I] [j].
Return dp[0] [0].
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[][] dp = new int[n + 1][n + 1];
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j); }}return dp[0] [0]; }}Copy the code6. Longest increasing subsequence of LeetCode300
Set the dynamic programming array dp[], and the ith state DP [I] represents the length of the longest ascending subsequence ending with the ith element. Dynamic programming boundary: DP [0]= 1; The length of the longest ascending subsequence LIS= 1; From 1 to n-1, loop I, calculate dp[I]; From 0 to i-1, cycle j, if NUMs [I]> NUMs [j], it indicates that NUMs [I] can be placed after NUMs [j], forming the longest ascending subsequence. If dp [I] < dp [j] + 1: dp [I] = dp [I] + 1, LIS for dp [0], dp [1],… dp[i]… , the largest in DP [n-1].
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if (len == 1) {
return 1;
}
int[] dp = new int[len];
Arrays.fill(dp, 1);
int LIS = 0;
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j] && dp[i]<dp[j] + 1) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
LIS = Math.max(LIS, dp[i]);
}
returnLIS; }}Copy the code7. LeetCode64 minimum path sum
Create a two-dimensional array dp, the same size as the original grid, dp[I] [j] represents the minimum sum of paths from the top left to (I,j). Obviously dp[0] [0]=grid[0] [0]. For the remaining elements in DP, the element values are calculated using the following state transition equation.
If I >0 and j=0, dp[I] [0]= DP [i-1] [0]+grid[I] [0].
When I =0 and j>0, dp[0] [j]= DP [0] [J-1]+grid[0] [J].
When I and j > > 0 0 dp [I] [j] = min (dp [j], [I – 1] dp [I]] [j – 1) + grid [I] [j].
Finally, the value of DP [m-1] [n-1] is the sum of the minimum paths from the upper left corner to the lower right corner of the grid.
class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length, columns = grid[0].length;
int[][] dp = new int[rows][columns];
dp[0] [0] = grid[0] [0];
for (int i = 1; i < rows; i++) {
dp[i][0] = dp[i - 1] [0] + grid[i][0];
}
for (int j = 1; j < columns; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; }}return dp[rows - 1][columns - 1]; }}Copy the codeLeetCode174 Dungeon game
Dp [I] [J] represents the minimum amount of health needed to reach the bottom right corner and keep at least 1 health during the walking process.
If the two dimensional array of representative dungeon for 1 * n or n * 1:1 * n, I from n – 2 to 0: dp [0] [I] = Max (1, dp [0] – [I + 1] dungeon [0] [I]); N * 1, I from n – 2 to 0: dp [I] [0] = Max (1, dp [0] – [I + 1] dungeon [I] [0]).
If the two-dimensional array representing the dungeon is N * M: I represents rows from n-2 to 0; J stands for columns, from m-2 to 0; Let dp_ min = min(dp[I + 1] [j], dp[I] [j+ 1]); Dp [I] [J] = Max (1, dp_ min-dungeon [I]).
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int row = dungeon.length;
int column = dungeon[0].length;
int[][] dp = new int[row][column];
dp[row-1][column-1]=Math.max(1.1-dungeon[row-1][column-1]);
for (int i = column -2; i >= 0; i--) {
dp[row-1][i] = Math.max(1,dp[row-1][i+1]-dungeon[row-1][i]);
}
for (int i = row -2; i >= 0; i--) {
dp[i][column-1] = Math.max(1,dp[i+1][column-1]-dungeon[i][column-1]);
}
for (int i = row -2; i >= 0; i--) {
for (int j = column -2; j >= 0; j--) {
int dp_min = Math.min(dp[i+1][j], dp[i][j+1]);
dp[i][j] = Math.max(1, dp_min-dungeon[i][j]); }}return dp[0] [0]; }}Copy the code