Dynamic Programming - 动态规划

    下面看看知乎上的熊大大对动规比较「正经」的描述。

    以上定义言简意赅，可直接用于实战指导，不愧是参加过NOI的。

    动规的思想虽然好理解，但是要真正活用起来就需要下点功夫了。建议看看下面知乎上的回答。

    1. 状态(状态不太好找，可先从转化方程入手分析)
    2. 状态间的转化方程(从题目的隐含条件出发寻找递推关系)

    其他的要点则是如初始化状态的确定(由状态和转化方程得知)，需要的结果(状态转移的终点)

    动态规划问题中一般从以下四个角度考虑：

    1. 状态(State)
    2. 状态间的转移方程(Function)
    3. 状态的初始化(Initialization)
    4. 返回结果(Answer)

    动规适用的情形：

    1. 最大值/最小值
    2. 有无可行解
    3. 求方案个数(如果需要列出所有方案，则一定不是动规，因为全部方案为指数级别复杂度，所有方案需要列出时往往用递归)
    4. 给出的数据不可随便调整位置

    单序列动态规划的状态通常定义为：数组前 i 个位置, 数字, 字母 或者 以第i个为… 返回结果通常为数组的最后一个元素。

    1. State: f[i] 前i个位置/数字/字母…
    2. Initialization: 根据题意进行必要的初始化
    3. Answer: f[n-1]

    双序列(DP_Two_Sequence)

    一般有两个数组或者两个字符串，计算其匹配关系。双序列中常用二维数组表示状态转移关系，但往往可以使用滚动数组的方式对空间复杂度进行优化。举个例子，以题 为例，状态转移方程如下：

    从以上转移方程可以看出 只与其前一个状态 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 并同时使用逆推，这是滚动数组使用的具体实践。

    代码如下：

    1. public class Solution {
    3.      * @param S, T: Two string.
    4.      * @return: Count the number of distinct subsequences
    5.      */
    6.     public int numDistinct(String S, String T) {
    7.         if (S == null || T == null) return 0;
    8.         if (S.length() < T.length()) return 0;
    9.         if (T.length() == 0) return 1;
    12.         for (int i = 0; i < S.length(); i++) {
    13.             for (int j = T.length() - 1; j >= 0; j--) {
    14.                 if (S.charAt(i) == T.charAt(j)) {
    15.                         f[j + 1] += f[j];
    16.                 }
    17.             }
    18.         }
    20.         return f[T.length()];
    22. }
    1. 什么是动态规划？动态规划的意义是什么？ - 知乎 - 熊大大和王勐的回答值得细看，适合作为动态规划的科普和入门。维基百科上对动态规划的描述感觉太过学术。
    2. - Topcoder上的一篇译作。