Week06

Jimmy-cod · Jimmy-cod · commit e88cce89b2be · 2020-07-16T23:42:04.000-04:00
diff --git a/.idea/leetcode/editor.xml b/.idea/leetcode/editor.xml
diff --git a/.idea/production/algorithm010/Week06/NOTE.md b/.idea/production/algorithm010/Week06/NOTE.md
diff --git a/Week06/LC120_triangle.java b/Week06/LC120_triangle.java
@@ -0,0 +1,39 @@
+package Week06;
+
+import java.util.List;
+
+public class LC120_triangle {
+    public int minimumTotal(List<List<Integer>> triangle) {
+
+        int n = triangle.size();
+        int m = triangle.get(n-1).size();
+
+        int[][] dp = new int[n+1][m+1];
+        for (int i=n-1;i>=0;i--){
+            //for (int j=0;j<triangle.get(i).size();j++){
+            for (int j=triangle.get(i).size()-1;j>=0;j--){
+                dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1]) + triangle.get(i).get(j);
+            }
+        }
+        return dp[0][0];
+    }
+
+/*
+* 可以用一维数组记录中间值；
+* 状态转移方程：f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
+* */
+    public int minimumTotal_2(List<List<Integer>> triangle) {
+
+        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<triangle.get(i).size();j++){
+            for (int j=triangle.get(i).size()-1;j>=0;j--){
+                dp[j]=Math.min(dp[j],dp[j+1]) + triangle.get(i).get(j);
+            }
+        }
+        return dp[0];
+    }
+}
diff --git a/Week06/LC62_unique_paths.java b/Week06/LC62_unique_paths.java
@@ -21,4 +21,20 @@ public int uniquePaths(int m, int n) {
         }
         return dp[n-1];
     }
+
+
+    public int uniquePaths_2(int m, int n) {
+        if (m <= 0 || n <= 0) {
+            return 0;
+        }
+        int[][] dp = new int[m+1][n+1];
+
+        dp[0][1]=1; // or  dp[1][0]=1;
+        for (int i=1;i<=m;i++){
+            for (int j=1;j<=n;j++){
+                dp[i][j] = dp[i-1][j] + dp[i][j-1];
+            }
+        }
+        return dp[m][n];
+    }
 }
diff --git a/Week06/LC70_climbing_stairs_ii.java b/Week06/LC70_climbing_stairs_ii.java
@@ -0,0 +1,49 @@
+package Week06;
+
+public class LC70_climbing_stairs_ii {
+
+    //每次你可以爬 1 或 2 或 3 个台阶
+    public int climbStairs(int n) {
+        // Dynamic Programming
+        if(n<=3) return n;
+
+        int[] dp = new int[n+1];
+        dp[0]=0;
+        dp[1]=1;
+        dp[2]=2;
+        dp[3]=4;
+
+        for(int i=4;i<=n;i++){
+            dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
+        }
+        return dp[n];
+    }
+
+    //每次你可以爬 1 或 2  个台阶,相邻不能重。如 1，1，2 或 122
+    public int climbStairs_3(int n) {
+        // Dynamic Programming
+        if(n<=3) return n;
+
+        int[] dp = new int[n+1];
+        dp[0]=0;
+        dp[1]=1;
+        dp[2]=1;
+        dp[3]=2;
+        dp[4]=2;
+
+        for(int i=5;i<=n;i++){
+            dp[i] = dp[i-1]-1+dp[i-2]-1;
+        }
+        return dp[n];
+    }
+
+}
+
+class Test{
+    public static void main(String[] args) {
+        LC70_climbing_stairs_ii s =new LC70_climbing_stairs_ii();
+        int res = s.climbStairs_3(7);
+
+        System.out.println("Result=" +res);
+    }
+}
diff --git a/Week06/NOTE.md b/Week06/NOTE.md
@@ -7,3 +7,14 @@
 共性：找到重复子问题
 
 差异性：最优子结构，中途可以淘汰次优解
+
+动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。
+第一步骤：定义数组元素的含义
+第二步骤：找出数组元素之间的关系式,最优子结构，把大的问题拆分成小的问题
+第三步骤：找出初始值
+优化: 保存的中间值是否可以覆盖，用一维数组保存中间值
+
+DP: 解题公式：
+a.分治（子问题）
+b.状态数组定义
+c.DP方程
