review-9_2

znn0301 · znn0301 · commit b4b3ba2b83a2 · 2020-12-07T18:42:22.000+08:00
diff --git a/src/main/java/com/chen/algorithm/znn/dynamic/test120/Solution.java b/src/main/java/com/chen/algorithm/znn/dynamic/test120/Solution.java
@@ -84,6 +84,24 @@ public void testCase() {
         triangle.add(Arrays.asList(4, 1, 8, 3));
 
         System.out.println(minimumTotal2(triangle));
+        System.out.println(minimumTotal3(triangle));
 
     }
+
+    public int minimumTotal3(List<List<Integer>> triangle) {
+        if (triangle == null || triangle.size() == 0) {
+            return 0;
+        }
+
+        int n = triangle.size();
+        int m = triangle.get(n - 1).size();
+        int[] dp = new int[m + 1];
+
+        for (int i = n - 1; i >= 0; i--) {
+            for (int j = 0; j <= i; j++) {
+                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
+            }
+        }
+        return dp[0];
+    }
 }
diff --git a/src/main/java/com/chen/algorithm/znn/dynamic/test64/Solution.java b/src/main/java/com/chen/algorithm/znn/dynamic/test64/Solution.java
@@ -17,12 +17,12 @@
  *
  * @Auther: zhunn
  * @Date: 2020/11/5 11:33
- * @Description: &#26368;&#23567;&#36335;&#24452;&#21644;&#65306;1-&#21160;&#24577;&#35268;&#21010;&#65307;2-&#21160;&#24577;&#35268;&#21010;-&#20248;&#21270;&#31354;&#38388;&#65292;&#20351;&#29992;&#21407;&#25968;&#32452;&#31354;&#38388;&#65307;3-&#21160;&#24577;&#35268;&#21010;-&#20248;&#21270;&#31354;&#38388;&#65292;&#19981;&#26356;&#25913;&#21407;&#25968;&#32452;(&#21487;&#24573;&#30053;)
+ * @Description: &#26368;&#23567;&#36335;&#24452;&#21644;&#65306;1-&#21160;&#24577;&#35268;&#21010;(&#25512;&#33616;)&#65307;2-&#21160;&#24577;&#35268;&#21010;-&#20248;&#21270;&#31354;&#38388;&#65292;&#20351;&#29992;&#21407;&#25968;&#32452;&#31354;&#38388;&#65307;3-&#21160;&#24577;&#35268;&#21010;-&#20248;&#21270;&#31354;&#38388;&#65292;&#19981;&#26356;&#25913;&#21407;&#25968;&#32452;(&#21487;&#24573;&#30053;)
  */
 public class Solution {
 
     /**
-     * 1-&#21160;&#24577;&#35268;&#21010;&#65292;&#23448;&#26041;&#35299;&#31572;
+     * 1-&#21160;&#24577;&#35268;&#21010;&#65292;&#23448;&#26041;&#35299;&#31572;(&#25512;&#33616;)
      *
      * @param grid
      * @return
@@ -107,6 +107,6 @@ public int minPathSum3(int[][] grid) {
     public void testCase() {
         int[][] nums = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
 
-        System.out.println(minPathSum2(nums));
+        System.out.println(minPathSum(nums));
     }
 }
diff --git a/src/main/java/com/chen/algorithm/znn/dynamic/test70/Solution.java b/src/main/java/com/chen/algorithm/znn/dynamic/test70/Solution.java
@@ -86,5 +86,28 @@ public int climbStairs2(int n) {
     public void test() {
         int res = climbStairs2(10);
         System.out.println(res);
+        int res3 = climbStairs3(10);
+        System.out.println(res3);
+    }
+
+    public int climbStairs3(int n) {
+        if (n <= 0) {
+            return 0;
+        }
+        if (n == 1) {
+            return 1;
+        }
+        if (n == 2) {
+            return 2;
+        }
+
+        int[] dp = new int[n + 1];
+        dp[0] = 0;
+        dp[1] = 1;
+        dp[2] = 2;
+        for (int i = 3; i <= n; i++) {
+            dp[i] = dp[i - 1] + dp[i - 2];
+        }
+        return dp[n];
     }
 }
diff --git a/src/main/java/com/chen/algorithm/znn/note b/src/main/java/com/chen/algorithm/znn/note
@@ -193,16 +193,16 @@ dynamic
                                                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);dp[i][2] = dp[i - 1][1] + prices[i];
 714&#12289; &#21487;&#20197;&#20080;&#21334;(&#20132;&#26131;)&#22810;&#27425;&#65292;&#19968;&#27425;&#20080;&#21334;&#21547;&#19968;&#27425;&#25163;&#32493;&#36153;
 (&#32929;&#31080;&#20080;&#21334;&#31995;&#21015; end)
-70. &#29228;&#27004;&#26799; ***
-120. &#19977;&#35282;&#24418;&#26368;&#23567;&#36335;&#24452;&#21644; ***
-64. &#26368;&#23567;&#36335;&#24452;&#21644; ***
+70. &#29228;&#27004;&#26799; ***                     1-&#36845;&#20195;&#65292;2-&#21160;&#24577;&#35268;&#21010;&#65292;dp[i] = dp[i - 1] + dp[i - 2];
+120. &#19977;&#35282;&#24418;&#26368;&#23567;&#36335;&#24452;&#21644; ***           for(int i = n - 1; i >= 0; i--);for(int j = 0; j <= i; j++);dp[j]=Math.min(dp[j],dp[j+1]) + triangle.get(i).get(j);
+64. &#26368;&#23567;&#36335;&#24452;&#21644; ***                 &#21021;&#22987;&#21270;dp[0][0] = grid[0][0];&#21021;&#22987;&#21270;&#31532;0&#34892;&#21644;&#31532;0&#21015;&#65292;for(int j=1;j<cols;j++);dp[i][j]=Math.min(dp[i-1][j], dp[i][j-1])+grid[i][j];
+62. &#19981;&#21516;&#36335;&#24452; ***
 53. &#26368;&#22823;&#23376;&#24207;&#21644; ***
-152. &#20056;&#31215;&#26368;&#22823;&#23376;&#25968;&#32452;***
 300. &#26368;&#38271;&#19978;&#21319;&#23376;&#24207;&#21015; ***
-72. &#32534;&#36753;&#36317;&#31163; ***
-62. &#19981;&#21516;&#36335;&#24452; ***
+152. &#20056;&#31215;&#26368;&#22823;&#23376;&#25968;&#32452;***
 279. &#23436;&#20840;&#24179;&#26041;&#25968; ***
 343. &#25972;&#25968;&#25286;&#20998; ***
+72. &#32534;&#36753;&#36317;&#31163; ***
 198. &#25171;&#23478;&#21163;&#33293; ***
 213. &#25171;&#23478;&#21163;&#33293; II ***
 337. &#25171;&#23478;&#21163;&#33293; III ***

Original file line number	Diff line number	Diff line change
`@@ -17,12 +17,12 @@`
`17`	`17`	`*`
`18`	`18`	`* @Auther: zhunn`
`19`	`19`	`* @Date: 2020/11/5 11:33`
`20`		`- * @Description: 最小路径和：1-动态规划；2-动态规划-优化空间，使用原数组空间；3-动态规划-优化空间，不更改原数组(可忽略)`
	`20`	`+ * @Description: 最小路径和：1-动态规划(推荐)；2-动态规划-优化空间，使用原数组空间；3-动态规划-优化空间，不更改原数组(可忽略)`
`21`	`21`	`*/`
`22`	`22`	`public class Solution {`
`23`	`23`
`24`	`24`	`/**`
`25`		`- * 1-动态规划，官方解答`
	`25`	`+ * 1-动态规划，官方解答(推荐)`
`26`	`26`	`*`
`27`	`27`	`* @param grid`
`28`	`28`	`* @return`
`@@ -107,6 +107,6 @@ public int minPathSum3(int[][] grid) {`
`107`	`107`	`public void testCase() {`
`108`	`108`	`int[][] nums = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};`
`109`	`109`
`110`		`- System.out.println(minPathSum2(nums));`
	`110`	`+ System.out.println(minPathSum(nums));`
`111`	`111`	`}`
`112`	`112`	`}`
-Original file line number
+Diff line change
                                                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);dp[i][2] = dp[i - 1][1] + prices[i];
 、 可以买卖(交易)多次，一次买卖含一次手续费
 (股票买卖系列 end)
 -70. 爬楼梯 ***
 -120. 三角形最小路径和 ***
 -64. 最小路径和 ***
 +70. 爬楼梯 ***                     1-迭代，2-动态规划，dp[i] = dp[i - 1] + dp[i - 2];
 +120. 三角形最小路径和 ***           for(int i = n - 1; i >= 0; i--);for(int j = 0; j <= i; j++);dp[j]=Math.min(dp[j],dp[j+1]) + triangle.get(i).get(j);
 +64. 最小路径和 ***                 初始化dp[0][0] = grid[0][0];初始化第0行和第0列，for(int j=1;j<cols;j++);dp[i][j]=Math.min(dp[i-1][j], dp[i][j-1])+grid[i][j];
 +62. 不同路径 ***
 . 最大子序和 ***
 -152. 乘积最大子数组***
 . 最长上升子序列 ***
 -72. 编辑距离 ***
 -62. 不同路径 ***
 +152. 乘积最大子数组***
 . 完全平方数 ***
 . 整数拆分 ***
 +72. 编辑距离 ***
 . 打家劫舍 ***
 . 打家劫舍 II ***
 . 打家劫舍 III ***