[dynamic programming] Yan’s DP analysis
Yan's DP analysis and explanation from acwing yxc. This paper is a note of several classic examples @ H_ 502_ 2@
@H_ 502_ 2@
53. Maximum subsequence sum
Given an integer array nums, find a continuous subarray with the largest sum (the subarray contains at least one element) and return its maximum sum. @ h_502_2@
Example: @ h_ 502_ 2@
输入: [-2,1,-3,4,-1,2,-5,4]
输出: 6
解释: 连续子数组 [4,1] 的和最大，为 6。
Advanced: @ h_ 502_ 2@
If you have implemented a solution with complexity O (n), try using a more sophisticated divide and conquer method@ H_ 502_ 2@
Status representation: \ (f [i] \) indicates that the sum of the largest continuous subsequences ending with the ith number@ H_ 502_ 2@
Attribute represented by state: Max max@ H_ 502_ 2@
Initialization: \ (f [0] = nums [0] \) @ h_ 502_ 2@
Partition of set [transfer equation]: \ (f [i] = max (f [I - 1], 0) + nums [i] \) @ h_ 502_ 2@
Return result: \ (RES = max (f [0], f [1], f [2]... F [n]) \) @ h_ 502_ 2@
public int maxSubArray(int[] nums) {
int[] f = new int[nums.length];
f[0] = nums[0];
int res = f[0];
for(int i = 1; i < nums.length; i++){
f[i] = Math.max(f[i - 1],0) + nums[i];
res = Math.max(res,f[i]);
}
return res;
}
Time complexity: the number of States is O (n), the transition time is O (1), and the total time is O (n)@ H_ 502_ 2@
Space complexity: additional o (n) space is required to store the state@ H_ 502_ 2@
Optimization: the storage space complexity of the array is replaced by variables and optimized to constants@ H_ 502_ 2@
public int maxSubArray(int[] nums) {
int res = Integer.MIN_VALUE,prev = 0;
for(int i = 0; i < nums.length; i++){
int Now = Math.max(prev,0) + nums[i];
res = Math.max(Now,res);
prev = Now;
}
return res;
}
120. Triangle minimum path and
Given a triangle, find the minimum path sum from top to bottom. Each step can only move to the adjacent nodes in the next row@ H_ 502_ 2@
Adjacent nodes here refer to two nodes whose subscript is the same as or equal to the subscript + 1 of the previous node@ H_ 502_ 2@
For example, given triangle: @ h_ 502_ 2@
[
[2],[3,4],[6,5,7],[4,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). @ h_502_2@
Description: @ h_ 502_ 2@
If you can only use the extra space of O (n) (n is the total number of triangles) to solve this problem, your algorithm will score extra points. @ h_502_2@
Status representation: $f [i] [J] $represents all paths @ h from the starting point to the i-th line and the j-th number_ 502_ 2@
Attribute represented by status: the minimum value of the sum of numbers on all paths@ H_ 502_ 2@
Initialization: \ (f [0] [0] = t.get (0) get(0)\)@H_ 502_ 2@
Partition of set [transfer equation]: @ h_502_2@
Return result: \ (RES = min (f [n-1] [1 - > n-1]) \) @ h_ 502_ 2@
public int minimumTotal(List<List<Integer>> t) {
int n = t.size();
int[][] f = new int[2][n]; //f[i][j]代表从起点走到第i行第j列的最小值
f[0][0] = t.get(0).get(0);
for(int i = 1; i < n; i ++){
for(int j = 0; j <= i ; j ++){
f[i&1][j] = Integer.MAX_VALUE;
if(j > 0) f[i&1][j] = Math.min(f[i&1][j],f[i-1&1][j-1]+t.get(i).get(j));//代表上下层坐标相等的情况
if( j < i) f[i&1][j] = Math.min(f[i&1][j],f[i-1&1][j]+t.get(i).get(j));//代表是上层下层坐标相等的情况
}
}
int res = Integer.MAX_VALUE;
for(int i = 0; i< n; i++){
res = Math.min(res,f[n-1&1][i]);
}//返回结果为最后一层的最小值 min(f[n-1][0->n-1])
return res;
}
91. Decoding method
A message containing the letters A-Z is encoded in the following way: @ h_ 502_ 2@
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non empty string containing only numbers, calculate the total number of decoding methods@ H_ 502_ 2@
Example 1: @ h_ 502_ 2@
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
Example 2: @ h_ 502_ 2@
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26),"VF" (22 6),或者 "BBF" (2 2 6) 。
Status representation: \ (f [i] \) represents all strings decoded from the first I digits@ H_ 502_ 2@
Attribute represented by status: quantity@ H_ 502_ 2@
Initialization: \ (f [0] = 1 \) @ h_ 502_ 2@
Partition of set [transfer equation]: @ h_502_2@
Return result: \ (RES = f [n] \) @ h_ 502_ 2@
public int numDecodings(String s) {
int n = s.length();
int[] f = new int[n + 1]; //减少边界的判断
char[] chs = s.tocharArray();
f[0] = 1;
for(int i = 1; i<= n ; i++){
if( chs[i - 1]!= '0') f[i] += f[i - 1];
if(i >= 2){
int t = (chs[i - 2] -'0') * 10 + chs[i - 1] -'0';
if( t>= 10 && t<=26) f[i] += f[i - 2];
}
}
return f[n];
}
62. Different paths
A robot is located in the upper left corner of an M x n grid (the starting point is marked "start" in the figure below). @ h_502_2@
The robot can only move down or right one step at a time. The robot attempts to reach the lower right corner of the grid (marked "finish" in the figure below). @ h_502_2@
How many different paths are there altogether@ H_ 502_ 2@
@H_ 502_ 2@@H_ 502_ 2@
For example, the above figure is a 7 x 3 grid. How many possible paths are there@ H_ 502_ 2@
Example 1: @ h_ 502_ 2@
输入: m = 3,n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
Example 2: @ h_ 502_ 2@
输入: m = 7,n = 3
输出: 28
Tip: @ h_ 502_ 2@
Status indication: $f [i] [J] \ (indicates all paths @ h from the starting point to \ [I, J] $_ 502_ 2@
Attribute represented by status: number of paths@ H_ 502_ 2@
Initialization: the first row and the first column are on the boundary, and the path is 1, so f [0] [J] and f [i] [0] are both 1@ H_ 502_ 2@
Partition of set [transfer equation]: @ h_502_2@
Return result: \ (RES = f [I-1] [J-1] \) @ h_ 502_ 2@
public int uniquePaths(int m,int n) {
//f[m,n]表示走到m,n的路径 res = f[m-1][n-1]
int[][] f = new int[m][n];
for(int i = 0; i < m; i ++){
for(int j = 0; j < n; j++){
if(i == 0 || j == 0) f[i][j] = 1;
else f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[m - 1][n - 1];
}
63. Different paths II
A robot is located in the upper left corner of an M x n grid (the starting point is marked "start" in the figure below). @ h_502_2@
The robot can only move down or right one step at a time. The robot attempts to reach the lower right corner of the grid (marked "finish" in the figure below). @ h_502_2@
Now consider that there are obstacles in the mesh. How many different paths will there be from the upper left corner to the lower right corner@ H_ 502_ 2@
@H_ 502_ 2@@H_ 502_ 2@
The obstacles and empty positions in the grid are represented by 1 and 0 respectively@ H_ 502_ 2@
Note: the values of M and n do not exceed 100@ H_ 502_ 2@
Example 1: @ h_ 502_ 2@
输入:
[
[0,0],[0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
Status indication: $f [i] [J] \ (indicates all paths @ h from the starting point to \ [I, J] $_ 502_ 2@
Attribute represented by status: number of paths@ H_ 502_ 2@
Initialization: the number of paths in the first row and the first column@ H_ 502_ 2@
Partition of set [transfer equation]: @ h_502_2@
Return result: \ (RES = f [I-1] [J-1] \) @ h_ 502_ 2@
class Solution {
public int uniquePathsWithObstacles(int[][] g) {
if (g == null || g.length == 0) {
return 0;
}
// 定义 dp 数组并初始化第 1 行和第 1 列。
int m = g.length,n = g[0].length;
int[][] f = new int[m][n];
for(int i = 0; i < m && g[i][0] != 1; i++){ //为第一行的路径赋值，直到遇到障碍物
f[i][0] = 1;
}
for(int i = 0; i < n && g[0][i] != 1; i++){//为第一列的路径赋值，直到遇到障碍物
f[0][i] = 1;
}
for(int i = 1; i < m; i ++){
for(int j = 1; j < n; j++){
if(g[i][j] == 1) continue; //如果遇到障碍物，跳过，默认为0
else{
f[i][j] = f[i - 1][j] + f[i][j - 1];//等于上面来的+左面来的
}
}
}
return f[m - 1][n - 1];
}
}
Another way: @ h_ 502_ 2@
public int uniquePathsWithObstacles(int[][] g) {
if (g == null || g.length == 0) {
return 0;
}
// 定义 dp 数组并初始化第 1 行和第 1 列。
int m = g.length,n = g[0].length;
int[][] f = new int[m][n];
for(int i = 0; i < m; i ++){
for(int j = 0; j < n; j++){
if(g[i][j] == 1) continue; //遇到障碍物 跳过
if( i == 0 && j == 0 ) f[i][j] = 1; //左上角顶点处，初始化为1
if( i > 0 ) f[i][j] += f[i - 1][j];
if( j > 0 ) f[i][j] += f[i][j - 1];
}
}
return f[m - 1][n - 1];
}
198. House raiding
You are a professional thief who plans to steal houses along the street. There is a certain amount of cash hidden in each room. The only restrictive factor affecting your theft is that the adjacent houses are equipped with interconnected anti-theft systems. If two adjacent houses are intruded by thieves on the same night, the system will automatically alarm@ H_ 502_ 2@
Given a non negative integer array representing the amount stored in each house, calculate the maximum amount you can steal overnight without touching the alarm device@ H_ 502_ 2@
Example 1: @ h_ 502_ 2@
输入：[1,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
Example 2: @ h_ 502_ 2@
输入：[2,7,9,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2),偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
Tip: @ h_ 502_ 2@
public int rob(int[] nums) {
int n = nums.length;
int[] f = new int[n+1];//n+1 长度，不再需要考虑边界问题 [x,4 ....n] 1-n
int[] g = new int[n+1];
for(int i = 1; i <= n; i++){
f[i] = Math.max(f[i-1],g[i-1]);//f[i]代表没选num[i]的Max
g[i] = f[i-1]+nums[i-1]; // g[i]代表选nums[i]的选法max
}
return Math.max(f[n],g[n]);
}
72. Edit distance
Here are two words word1 and word2. Please calculate the minimum operands used to convert word1 to word2@ H_ 502_ 2@
You can do the following three operations on a word: @ h_ 502_ 2@
Example 1: @ h_ 502_ 2@
输入：word1 = "horse",word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
Example 2: @ h_ 502_ 2@
输入：word1 = "intention",word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
Status representation: $f [i] [J] \ (all schemes that change the first string \) I \ (letters into the second string \) J $letters @ h_ 502_ 2@
Attribute represented by status: minimum value@ H_ 502_ 2@
Initialization: one string is empty and the result is the length of the other string@ H_ 502_ 2@
Partition of set [transfer equation]: @ h_502_2@
Return result: $res = f [M] [n] $@ h_ 502_ 2@
public int minDistance(String word1,String word2) {
char[] ch1 = word1.tocharArray();
char[] ch2 = word2.tocharArray();
int n1 = word1.length(),n2 = word2.length();
int[][] f = new int[n1+1][n2+1];
for(int i = 0; i <= n1; i++) f[i][0] = i; //填边
for(int i = 0; i <= n2; i++) f[0][i] = i;
for(int i = 1; i <= n1 ; i++){
for(int j = 1; j<= n2; j++){
f[i][j] = Math.min(f[i-1][j],f[i][j-1])+1;// insert和delete
int rep = 0;//交换的操作
if(ch1[i-1] != ch2[j-1]){
rep = 1;
}
f[i][j] = Math.min(f[i][j],f[i-1][j-1]+rep); // replace or not
}
}
return f[n1][n2];
}