第六周作业

yuxiao-git · yuxiao-git · commit a1400b3565a4 · 2020-12-14T00:08:47.000+08:00
diff --git a/Week_06/LongestCommonSubsequence.java b/Week_06/LongestCommonSubsequence.java
@@ -0,0 +1,25 @@
+package Week_06;
+
+public class LongestCommonSubsequence {
+    public int longestCommonSubsequence(String text1, String text2) {
+        char[] s1 = text1.toCharArray();
+        char[] s2 = text2.toCharArray();
+
+        int l1 = s1.length + 1;
+        int l2 = s2.length + 1;
+
+        int[][] dp = new int[l1][l2];
+
+        for (int i = 1; i < l1; i++) {
+            for (int j = 1; j < l2; j++) {
+                if (s1[i - 1] == s2[j - 1]) {
+                    dp[i][j] = dp[i - 1][j - 1] + 1;
+                } else {
+                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
+                }
+            }
+        }
+        return dp[l1 - 1][l2 - 1];
+
+    }
+}
diff --git a/Week_06/MinimumTotal.java b/Week_06/MinimumTotal.java
@@ -0,0 +1,31 @@
+package Week_06;
+
+import java.util.List;
+
+public class MinimumTotal {
+    // 我擅长的动态规划 哈哈
+    /*public int minimumTotal(List<List<Integer>> triangle) {
+        int n = triangle.size();
+        int[] dp = new int[n + 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];
+    }*/
+
+    // 我不擅长的递归，尝试老师讲解的方式再写出来
+    public int minimumTotal(List<List<Integer>> triangle) {
+        return minimumTotalRec(triangle, 0, 0);
+    }
+
+    private int minimumTotalRec(List<List<Integer>> triangle, int level, int index) {
+        if (level == triangle.size() - 1) {// 到底层返回对应坐标值即可
+            return triangle.get(level).get(index);
+        }
+
+        return Math.min(minimumTotalRec(triangle, level + 1, index), minimumTotalRec(triangle, level + 1, index + 1)) + triangle.get(level).get(index);
+    }
+}
diff --git a/Week_06/README.md b/Week_06/README.md
@@ -1 +1,10 @@
-学习笔记
+##学习笔记
+
+1、本周内容主旨：动态规划
+    动态规划：上完第一节课及做完部分题目我的个人理解是每次走当前分步的最‘捷径’，直至所有分步结合。就是说如果动态规划方案无优劣区分，及一个极端那就是前面我们学过的'分治'.
+            他比较适合大数据类型的’最小路径和‘题目解法,当前状态和前继最优匹配达成当前最优，整个问题拆分一个个当前节点这样处理，那么所有当前节点合并结果即是动态规划解。
+            
+    通过这周三天学习及做题情况发现，动态规划至关重要是发现递推公式（数学归纳法）
+            
+        动态规划我的解法第一步分析题意，定义出合适的状态（一般需要着重考虑到的是空间复杂度），第二步则找出dp方程，dp方程我发现可至上向下顺序滚动，
+        或者至下向上逆向循环（一般这样也可以递归），而dp方程也有数学归纳法的一点应用，总体根据题目具体分析，下一步则是据此求解处理就可以啦。
diff --git a/Week_06/Rob.java b/Week_06/Rob.java
@@ -0,0 +1,27 @@
+package Week_06;
+
+// 打家劫舍（简单）
+public class Rob {
+    public int rob(int[] nums) {
+        int length = nums.length;
+        if (length == 0) {
+            return 0;
+        }
+
+        if (length == 1) {
+            return nums[0];
+        }
+
+        int resPre = nums[0];
+        int maxRes = Math.max(resPre, nums[1]);
+
+        for (int i = 2; i < length; i++) {
+            int temp = maxRes;
+            maxRes = Math.max(maxRes, resPre + nums[i]);
+            resPre = temp;
+        }
+
+        return maxRes;
+
+    }
+}
diff --git a/Week_06/Rob2.java b/Week_06/Rob2.java
@@ -0,0 +1,36 @@
+package Week_06;
+
+public class Rob2 {
+    public int rob(int[] nums) {
+        int length = nums.length;
+        if (length == 0) {
+            return 0;
+        }
+
+        int ignoreFirst = nums[nums.length - 1];
+        int ignoreLast = nums[0];
+        if (length <= 2) {
+            return Math.max(ignoreFirst, ignoreLast);
+        }
+
+        // 忽略第一个
+        int resPre = nums[1];
+        ignoreFirst = Math.max(resPre, nums[2]);
+        for (int i = 3; i < length; i++) {
+            int temp = ignoreFirst;
+            ignoreFirst = Math.max(ignoreFirst, resPre + nums[i]);
+            resPre = temp;
+        }
+
+        // 忽略最后一个
+        resPre = nums[0];
+        ignoreLast = Math.max(resPre, nums[1]);
+        for (int i = 2; i < length - 1; i++) {
+            int temp = ignoreLast;
+            ignoreLast = Math.max(ignoreLast, resPre + nums[i]);
+            resPre = temp;
+        }
+
+        return Math.max(ignoreFirst, ignoreLast);
+    }
+}
