Dynamic Programming - 动态规划
动态规划是一种「分治」的思想,通俗一点来说就是「大事化小,小事化无」的艺术。在将大问题化解为小问题的「分治」过程中,保存对这些小问题已经处理好的结果,并供后面处理更大规模的问题时直接使用这些结果。嗯,感觉讲了和没讲一样,还是不会使用动规的思想解题...
下面看看知乎上的熊大大对动规比较「正经」的描述。
动态规划是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。
以上定义言简意赅,可直接用于实战指导,不愧是参加过NOI的。
动规的思想虽然好理解,但是要真正活用起来就需要下点功夫了。建议看看下面知乎上的回答。
动态规划最重要的两个要点:
- 状态(状态不太好找,可先从转化方程入手分析)
- 状态间的转化方程(从题目的隐含条件出发寻找递推关系)
其他的要点则是如初始化状态的确定(由状态和转化方程得知),需要的结果(状态转移的终点)
动态规划问题中一般从以下四个角度考虑:
- 状态(State)
- 状态间的转移方程(Function)
- 状态的初始化(Initialization)
- 返回结果(Answer)
动规适用的情形:
- 最大值/最小值
- 有无可行解
- 求方案个数(如果需要列出所有方案,则一定不是动规,因为全部方案为指数级别复杂度,所有方案需要列出时往往用递归)
- 给出的数据不可随便调整位置
单序列(DP_Sequence)
单序列动态规划的状态通常定义为:数组前 i 个位置, 数字, 字母 或者 以第i个为... 返回结果通常为数组的最后一个元素。
按照动态规划的四要素,此类题可从以下四个角度分析。
- State: f[i] 前i个位置/数字/字母...
- Function: f[i] = f[i-1]... 找递推关系
- Initialization: 根据题意进行必要的初始化
- Answer: f[n-1]
双序列(DP_Two_Sequence)
一般有两个数组或者两个字符串,计算其匹配关系。双序列中常用二维数组表示状态转移关系,但往往可以使用滚动数组的方式对空间复杂度进行优化。举个例子,以题 Distinct Subsequences 为例,状态转移方程如下:
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]
的值。所以若想得到上一轮的结果,必须在内循环使用逆推的方式进行。文字表述比较模糊,可以自行画一个二维矩阵的转移矩阵来分析,认识到这一点非常重要。
小结一下,使用滚动数组的核心在于:
- 状态转移矩阵中只能取
f[i+1][*]
和f[i][*]
, 这是使用滚动数组的前提。 - 外循环使用 i, 内循环使用 j 并同时使用逆推,这是滚动数组使用的具体实践。
代码如下:
public class Solution {
/**
* @param S, T: Two string.
* @return: Count the number of distinct subsequences
*/
public int numDistinct(String S, String T) {
if (S == null || T == null) return 0;
if (S.length() < T.length()) return 0;
if (T.length() == 0) return 1;
int[] f = new int[T.length() + 1];
f[0] = 1;
for (int i = 0; i < S.length(); i++) {
for (int j = T.length() - 1; j >= 0; j--) {
if (S.charAt(i) == T.charAt(j)) {
f[j + 1] += f[j];
}
}
}
return f[T.length()];
}
}
纸上得来终觉浅,绝知此事要躬行。光说不练假把戏,下面就来几道DP的题练练手。
Reference
- 什么是动态规划?动态规划的意义是什么? - 知乎 - 熊大大和王勐的回答值得细看,适合作为动态规划的科普和入门。维基百科上对动态规划的描述感觉太过学术。
- 动态规划:从新手到专家 - Topcoder上的一篇译作。