[TOC] # Dynamic Progrmming - 动态规划 动态规划是一种「分治」的思想，通俗一点来说就是「大事化小，小事化无」的艺术。在将大问题化解为小问题的「分治」过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果。嗯，感觉讲了和没讲一样，还是不会使用动规的思想解题... 下面看看知乎上的熊大大对动规比较「正经」的描述。 > 动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。 以上定义言简意赅，可直接用于实战指导，不愧是参加过NOI的。 动规的思想虽然好理解，但是要真正活用起来就需要下点功夫了。建议看看下面知乎上的回答。 动态规划最重要的两个要点： 1. 状态(状态不太好找，可先从转化方程入手分析) 2. 状态间的转化方程(从题目的隐含条件出发寻找递推关系) 其他的要点则是如初始化状态的确定(由状态和转化方程得知)，需要的结果(状态转移的终点) 动态规划问题中一般从以下四个角度考虑： 1. 状态(State) 2. 状态间的转移方程(Function) 3. 状态的初始化(Initialization) 4. 返回结果(Answer) 动规适用的情形： 1. 最大值/最小值 2. 有无可行解 3. 求方案个数(如果需要列出所有方案，则一定不是动规，因为全部方案为指数级别复杂度，所有方案需要列出时往往用递归) 4. 给出的数据不可随便调整位置 ## 单序列(DP\_Sequence) 单序列动态规划的状态通常定义为：数组前 i 个位置, 数字, 字母 或者 以第i个为... 返回结果通常为数组的最后一个元素。 按照动态规划的四要素，此类题可从以下四个角度分析。 1. State: f\[i\] 前i个位置/数字/字母... 2. Function: f\[i\] = f\[i-1\]... 找递推关系 3. Initialization: 根据题意进行必要的初始化 4. Answer: f\[n-1\] ## 双序列(DP\_Two\_Sequence) 一般有两个数组或者两个字符串，计算其匹配关系。双序列中常用二维数组表示状态转移关系，但往往可以使用滚动数组的方式对空间复杂度进行优化。举个例子，以题[Distinct Subsequences](http://algorithm.yuanbin.me/zh-hans/dynamic_programming/distinct_subsequences.html)为例，状态转移方程如下： ~~~ f[i+1][j+1] = f[i][j+1] + f[i][j] (if S[i] == T[j]) f[i+1][j+1] = f[i][j+1] (if S[i] != T[j]) ~~~ 从以上转移方程可以看出`f[i+1][*]`只与其前一个状态`f[i][*]`有关，而对于`f[*][j]`来说则基于当前索引又与前一个索引有关，故我们以递推的方式省略第一维的空间，并以第一维作为外循环，内循环为 j, 由递推关系可知在使用滚动数组时，若内循环 j 仍然从小到大遍历，那么对于`f[j+1]`来说它得到的`f[j]`则是当前一轮(`f[i+1][j]`)的值，并不是需要的`f[i][j]`的值。所以若想得到上一轮的结果，必须在内循环使用逆推的方式进行。文字表述比较模糊，可以自行画一个二维矩阵的转移矩阵来分析，认识到这一点非常重要。 小结一下，使用滚动数组的核心在于： 1. 状态转移矩阵中只能取`f[i+1][*]`和`f[i][*]`, 这是使用滚动数组的前提。 2. 外循环使用 i, 内循环使用 j 并同时使用逆推，这是滚动数组使用的具体实践。 代码如下： ~~~python class Solution: def numDistinct(self, s: str, t: str) -> int: # dp[i][j] 表示s的前i位中能够匹配t的前j位的个数 # if s[i] == t[j]: dp[i][j] = dp[i-1][j-1] + dp[i-1][j] # else: dp[i][j] = dp[i-1][j] # ans = dp[n][m] n, m = len(s), len(t) dp = [[0 for j in range(m + 1)] for i in range(n + 1)] for i in range(n): dp[i][0] = 1 for j in range(m): for i in range(n): if s[i] == t[j]: dp[i+1][j+1] = dp[i][j] + dp[i][j+1] else: dp[i+1][j+1] = dp[i][j+1] return dp[n][m] ~~~ 纸上得来终觉浅，绝知此事要躬行。光说不练假把戏，下面就来几道DP的题练练手。 ### Reference 1. [billryan-动态规划](https://github.com/billryan/algorithm-exercise/blob/master/zh-hans/dynamic_programming/README.md#dynamic-programming---%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92)