作业：LeetCode第64题·最小路径和，第72题·编辑距离，以及第六周总结

WYebp · WYebp · commit 75ba9835b00a · 2020-07-19T19:17:53.000+08:00
diff --git a/Week06/LC_64_minPathSum.java b/Week06/LC_64_minPathSum.java
@@ -0,0 +1,22 @@
+/*
+ * @lc app=leetcode.cn id=64 lang=java
+ *
+ * [64] 最小路径和
+ */
+
+// @lc code=start
+class Solution {
+    public int minPathSum(int[][] grid) {
+        for(int i = 0; i < grid.length; i++) {
+            for(int j = 0; j < grid[0].length; j++) {
+                if(i == 0 && j == 0) continue;
+                else if(i == 0)  grid[i][j] = grid[i][j - 1] + grid[i][j];
+                else if(j == 0)  grid[i][j] = grid[i - 1][j] + grid[i][j];
+                else grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
+            }
+        }
+        return grid[grid.length - 1][grid[0].length - 1];
+    }
+}
+// @lc code=end
+
diff --git a/Week06/LC_72_minDistance.java b/Week06/LC_72_minDistance.java
@@ -0,0 +1,28 @@
+/*
+ * @lc app=leetcode.cn id=72 lang=java
+ *
+ * [72] 编辑距离
+ */
+
+// @lc code=start
+class Solution {
+    public int minDistance(String word1, String word2) {
+        int n1 = word1.length();
+        int n2 = word2.length();
+        int[][] dp = new int[n1 + 1][n2 + 1];
+        // 第一行
+        for (int j = 1; j <= n2; j++) dp[0][j] = dp[0][j - 1] + 1;
+        // 第一列
+        for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;
+
+        for (int i = 1; i <= n1; i++) {
+            for (int j = 1; j <= n2; j++) {
+                if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
+                else dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
+            }
+        }
+        return dp[n1][n2];
+    }
+}
+// @lc code=end
+
diff --git a/Week06/NOTE.md b/Week06/NOTE.md
@@ -1 +1,173 @@
-学习笔记
+学习笔记
+
+
+
+# 动态规划
+
+> 动态规划 Dynamic Programming
+>
+> 20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。
+>
+> 动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果
+
+## 1.定义
+
+- 运筹学的一个分支，是求解决策过程最优化的过程
+
+- 主要用于求解以时间划分阶段的动态过程的优化问题
+
+  > - 但是一些与时间无关的静态规划(如线性规划、[非线性规划](https://baike.baidu.com/item/非线性规划))，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解
+
+- 解决多阶段决策最优化的过程称为动态规划方法
+
+  > - 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。
+  > - 因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。
+  > - 当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。
+  > - 这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为**多阶段决策**过程，这种问题称为多阶段决策问题。
+  > - 在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义
+
+## 2.术语
+
+### 1.阶段
+
+- 把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同
+
+- 描述阶段的变量称为**阶段变量**
+
+  > - 在多数情况下，阶段变量是离散的，用k表示。
+  > - 此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的 
+
+
+
+### 2.状态
+
+- 状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素
+
+  > 比如，某阶段的出发位置，就是状态，它既是该阶段某路的起点，同时又是前一阶段某支路的终点 
+
+
+
+### 3.无后效性
+
+- 我们要求状态具有下面的性质：
+
+  - 如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响
+  - 所有各阶段都确定时，整个过程也就确定了
+
+  > 换句话说，过程的每一次实现可以用一个状态序列表示，比如每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。
+  >
+  > 从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。
+
+  
+
+- 状态的这个性质意味着**过程的历史只能通过当前的状态去影响它的未来的发展**，这个性质称为**无后效性**。
+
+
+
+### 4.决策
+
+- 一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种**选择（行动）**称为决策
+
+  > - 在最优控制中，也称为控制
+  > - 在许多问题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。
+
+- 描述决策的变量称**决策变量**，因状态满足无后效性，故在每个阶段选择决策时**只需考虑当前的状态**而无须考虑过程的历史
+
+- 决策变量的范围称为**允许决策集合**
+
+
+
+### 5.策略
+
+- 由每个阶段的决策组成的序列称为策略
+- 对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合
+- 允许策略集合中达到最优效果的策略称为**最优策略** 
+
+
+
+### 6.状态转移方程
+
+#### 1.定义
+
+- 给定`k`阶段**状态变量**`x(k)`的值后，如果这一阶段的**决策变量**一经确定，第`k+1`阶段的状态变量`x(k+1)`也就完全确定
+- 即`x(k+1)`的值随`x(k)`和第`k`阶段的决策`u(k)`的值变化而变化，那么可以把这一关系看成`(x(k)，u(k))与x(k+1)`确定的对应关系
+- 用`x(k+1)=Tk(x(k),u(k))`表示
+- 这就是从`k`阶段到`k+1`阶段的状态转移规律，称为**状态转移方程 **
+
+
+
+### 7.最优化原理
+
+- 最优化原理：作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略” 
+- 最优性原理实际上是要求问题的最优策略的子策略也是最优
+
+
+
+## 3.与分治区别
+
+### 1.关键点
+
+- 动态规划 和 递归或者分治 没有根本上的区别（关键看有无最优的子结构） 
+- 共性：找到重复子问题
+- 差异性：最优子结构、中途可以淘汰次优解
+
+### 2.子问题
+
+> 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。
+>
+> 与[分治法](https://baike.baidu.com/item/分治法)类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
+
+- 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。
+- 如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。
+- 我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是**动态规划法的基本思路**。
+- 具体的动态规划算法多种多样，但它们具有相同的填表格式
+
+> 1.Wiki 定义： https://en.wikipedia.org/wiki/Dynamic_programming  、
+>
+> 2.“Simplifying a complicated problem by breaking it down into simpler sub-problems” (in a recursive manner) 
+>
+> 3.Divide & Conquer + Optimal substructure 分治 + 最优子结构
+
+
+
+## 4.适用条件
+
+任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。
+
+**1、**[**最优化原理**](https://baike.baidu.com/item/最优化原理)**（最优子结构性质）**
+
+最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，**一个最优化策略的子策略总是最优的**。一个问题满足最优化原理又称其具有最优子结构性质。
+
+**2、**[**无后效性**](https://baike.baidu.com/item/无后效性)
+
+将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，**每个状态都是过去历史的一个完整总结**。这就是无后向性，又称为无后效性。
+
+**3、子问题的重叠性**
+
+动态规划算法的**关键在于解决冗余**，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不**存储产生过程中的各种状态**，所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。
+
+
+
+## 5.分类
+
+- 动态规划的数学模型。根据决策过程的演变是确定性的还是随机性的。可分为**确定性决策过程**和**随机性决策过程**。另外。也可按时间参量是离散的或是连续的变量。分为**离散决策过程**和**连续决策过程**。
+
+- 组合起来就有**离散确定性．离散随机性．连续确定性．连续随机性**四种决策过程模型。
+
+对于确定性的决策过程。问题中`下一段的状态`已由当前段的状态及决策完全确定。
+
+对于随机性决策过程。它与确定性决策过程的区别在于下一段的状态并不能由当前段的状态及决策完全确定。而是**按某种概率分布**来决定下一段的状态。`这种概率分布`是由当前段的状态和决策完全确定。即间接方式决定下一阶段的状态。
+
+
+
+## 6.局限性
+
+- 它没有统一的处理方法，必须根据问题的各种性质并结合一定的技巧来处理；
+- 另外当变量的维数增大时，总的计算量及存贮量急剧增大。因而，受计算机的存贮量及计算速度的限制，当今的计算机仍不能用动态规划方法来解决较大规模的问题，这就是“**维数障碍**”
+
+
+
+## 7.扩展
+
+- B 站搜索： mit 动态规划
+  - https://www.bilibili.com/video/av53233912?from=search&seid=2847395688604491997
