第六周做野

邵联飞 · 邵联飞 · commit 3211e072530b · 2020-07-19T22:12:09.000+08:00
diff --git a/Week06/NOTE.md b/Week06/NOTE.md
@@ -1 +1,48 @@
-学习笔记
+学习笔记
+
+本周学习动态规划
+复习递归的伪代码
+java
+public void recur(int level, int param) { 
+  // terminator 递归的结束条件
+  if (level > MAX_LEVEL) { 
+    // process result 
+    return; 
+  }
+  // process current logic   处理当前节点
+  process(level, param); 
+  // drill down 进入下一节点
+  recur( level: level + 1, newParam);  
+  // restore current status  处理返回
+ 
+}
+
+分治的伪代码
+C/C++
+int divide_conquer(Problem *problem, int params) {
+  // recursion terminator
+  if (problem == nullptr) {
+    process_result
+    return return_result;
+  } 
+
+  // process current problem
+  subproblems = split_problem(problem, data)
+  subresult1 = divide_conquer(subproblem[0], p1)
+  subresult2 = divide_conquer(subproblem[1], p1)
+  subresult3 = divide_conquer(subproblem[2], p1)
+  ...
+
+  // merge
+  result = process_result(subresult1, subresult2, subresult3)
+  // revert the current level status
+ 
+  return 0;
+}
+
+
+定义：讲一个复杂的问题，将它分解为简单的子问题（用递归的方式）
+关键点：
+1.动态规划与递归或者分治没有本质上的区别(关键看有无最优的子结构)
+2.共性：找到重复子问题
+3.差异性：最优子结构，中途可淘汰次优解
diff --git a/Week06/first.java b/Week06/first.java
@@ -0,0 +1,34 @@
+
+//题目：回文子串
+//动态规划法
+class Solution {
+    public int countSubstrings(String s) {
+        if (s == null || s.equals("")) {
+            return 0;
+        }
+        int n = s.length();
+        boolean[][] dp = new boolean[n][n];
+        int result = s.length();
+        for (int i = 0; i < n; i++) dp[i][i] = true;
+        for (int i = n - 1; i >= 0; i--) {
+            for (int j = i + 1; j < n; j++) {
+                if (s.charAt(i) == s.charAt(j)) {
+                    if (j - i == 1) {
+                        dp[i][j] = true;
+                    } else {
+                        dp[i][j] = dp[i + 1][j - 1];
+                    }
+                } else {
+                    dp[i][j] = false;
+                }
+                if (dp[i][j]) {
+                    result++;
+                }
+            }
+        }
+        return result;
+
+    }
+}
+
+
diff --git a/Week06/second.java b/Week06/second.java
@@ -0,0 +1,38 @@
+
+//题目： 最大正方形
+
+
+struct Node{
+        int row_nums;
+        int col_nums;
+        Node():row_nums(0), col_nums(0){}
+        };
+
+class Solution {
+    public:
+    int maximalSquare(vector<vector<char>>& matrix) {
+        if(matrix.empty() || matrix[0].empty()) return 0;
+        int rows = matrix.size(), cols = matrix[0].size();
+        // 1. 确定dp数组和状态
+        vector<vector<Node>> dp(rows+1, vector<Node>(cols+1));
+        // 2. base case(dp[0][...]=0 & dp[...][0]=0)
+        // 3. 状态转移方程
+        for(int i = 1; i <= rows; i++){
+            for(int j = 1; j <= cols; j++){
+                if(matrix[i-1][j-1] == '1'){
+                    dp[i][j].row_nums = min(dp[i-1][j].row_nums, dp[i-1][j-1].row_nums)+1;
+                    dp[i][j].col_nums = min(dp[i][j-1].col_nums, dp[i-1][j-1].col_nums)+1;
+                }
+            }
+        }
+        // 4. 遍历dp计算最大正方形
+        int max_size = 0;
+        for(int i = 1; i <= rows; i++){
+            for(int j = 1; j <= cols; j++){
+                int edge = min(dp[i][j].row_nums, dp[i][j].col_nums);
+                max_size = max(max_size, edge*edge);
+            }
+        }
+        return max_size;
+    }
+};
