动态规划 — pydata: Huiming's learning notes

动态规划的本质，是对问题状态的定义和状态转移方程的定义。

引自维基百科

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。如何拆分问题，是动态规划的核心。而拆分问题，靠的就是状态的定义和状态转移方程的定义。

什么是状态的定义？

首先想说大家千万不要被下面的数学式吓到，这里只涉及到了函数相关的知识。我们先来看一个动态规划的教学必备题：

给定一个数列，长度为N，求这个数列的最长上升（递增）子数列（LIS）的长度.

以1 7 2 8 3 4为例, 这个数列的最长递增子数列是 1 2 3 4，长度为4；

次长的长度为3，包括 1 7 8; 1 2 3 等.

要解决这个问题，我们首先要定义这个问题和这个问题的子问题。

我们来重新定义这个问题：

给定一个数列，长度为 $N <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>N</mi></math>$ ，

设 $F k <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>k</mi></msub></math>$ 为：以数列中第 $k <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$ 项结尾的最长递增子序列的长度.

求 $F 1, . . ., F N <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mn>1</mn></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>F</mi><mi>N</mi></msub></math>$ 中的最大值.

显然，这个新问题与原问题等价。

而对于 $F k <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>k</mi></msub></math>$ 来讲， $F 1, . . ., F k - 1 <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mn>1</mn></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>F</mi><mrow data-mjx-texclass="ORD"><mi>k</mi><mo>-</mo><mn>1</mn></mrow></msub></math>$ 都是 $F k <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>k</mi></msub></math>$ 的子问题：因为以第 $k <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$ 项结尾的最长递增子序列（下称LIS），包含着以第 $1, . . ., k - 1 <math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><mi>k</mi><mo>-</mo><mn>1</mn></math>$ 中某项结尾的LIS。

上述的新问题 $F k <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>k</mi></msub></math>$ 也可以叫做状态，定义中的“ $F k <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>k</mi></msub></math>$ 为数列中第 $k <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$ 项结尾的LIS的长度”，就叫做对状态的定义。

之所以把 $F k <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>k</mi></msub></math>$ 做“状态”而不是“问题” ，一是因为避免跟原问题中“问题”混淆，二是因为这个新问题是数学化定义的。

什么是状态转移方程？

上述状态定义好之后，状态和状态之间的关系式，就叫做状态转移方程。

比如，对于LIS问题，我们的第一种定义：

设 $F k <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>k</mi></msub></math>$ 为：以数列中第 $k <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$ 项结尾的最长递增子序列的长度.

设 $A <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>A</mi></math>$ 为题中数列，状态转移方程为：

$F 1 = 1 <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mn>1</mn></msub><mo>=</mo><mn>1</mn></math>$ （根据状态定义导出边界情况）

$F k = m a x (F i + 1 | A k > A i, i \in (1, . . ., k - 1)), (k > 1) <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>k</mi></msub><mo>=</mo><mi>m</mi><mi>a</mi><mi>x</mi><mo stretchy="false">(</mo><msub><mi>F</mi><mrow data-mjx-texclass="ORD"><mi>i</mi></mrow></msub><mo>+</mo><mn>1</mn><mrow data-mjx-texclass="ORD"><mo stretchy="false">|</mo></mrow><msub><mi>A</mi><mrow data-mjx-texclass="ORD"><mi>k</mi></mrow></msub><mo>></mo><msub><mi>A</mi><mrow data-mjx-texclass="ORD"><mi>i</mi></mrow></msub><mo>,</mo><mi>i</mi><mo>\in</mo><mo stretchy="false">(</mo><mn>1</mn><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><mi>k</mi><mo>-</mo><mn>1</mn><mo stretchy="false">)</mo><mo stretchy="false">)</mo><mo>,</mo><mo stretchy="false">(</mo><mi>k</mi><mo>></mo><mn>1</mn><mo stretchy="false">)</mo></math>$

用文字解释一下是：以第 $k <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$ 项结尾的LIS的长度是：保证第 $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ 项比第 $k <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$ 项小的情况下，以第 $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ 项结尾的LIS长度加一的最大值，取遍 $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ 的所有值（ $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ 小于 $k <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$ ）。

这里可以看出，这里的状态转移方程，就是定义了问题和子问题之间的关系。

可以看出，状态转移方程就是带有条件的递推式。

alt text

def lengthOfLIS(nums):
    #Edge condition
    if not nums:
        return 0
    dp = [1 for i in xrange(len(nums))]
    for k in xrange(len(nums)):
        for i in xrange(k):
            # compare all F_i with F_k for i <ｋ
            if nums[i] < nums[k]:
                if dp[i] + 1 > dp[k]:
                    dp[k] = dp[i] + 1
    return max(dp)

lengthOfLIS([1, 7, 2, 8, 3, 4])

动态规划迷思

本题下其他用户的回答跟动态规划都有或多或少的联系，我也讲一下与本答案的联系。

a. “缓存”，“重叠子问题”，“记忆化”：

这三个名词，都是在阐述递推式求解的技巧。以Fibonacci数列为例，计算第100项的时候，需要计算第99项和98项；在计算第101项的时候，需要第100项和第99项，这时候你还需要重新计算第99项吗？不需要，你只需要在第一次计算的时候把它记下来就可以了。

上述的需要再次计算的“第99项”，就叫“重叠子问题”。如果没有计算过，就按照递推式计算，如果计算过，直接使用，就像“缓存”一样，这种方法，叫做“记忆化”，这是递推式求解的技巧。这种技巧，通俗的说叫“花费空间来节省时间”。都不是动态规划的本质，不是动态规划的核心。

b. “递归”：递归是递推式求解的方法，连技巧都算不上。

c. "无后效性"，“最优子结构”：

上述的状态转移方程中，等式右边不会用到下标大于左边 $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ 或者 $k <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math>$ 的值，这是"无后效性"的通俗上的数学定义，符合这种定义的状态定义，我们可以说它具有“最优子结构”的性质，在动态规划中我们要做的，就是找到这种“最优子结构”。

在对状态和状态转移方程的定义过程中，满足“最优子结构”是一个隐含的条件（否则根本定义不出来）。

需要注意的是，一个问题可能有多种不同的状态定义和状态转移方程定义，存在一个有后效性的定义，不代表该问题不适用动态规划。这也是其他几个答案中出现的逻辑误区：

动态规划方法要寻找符合“最优子结构“的状态和状态转移方程的定义，在找到之后，这个问题就可以以“记忆化地求解递推式”的方法来解决。而寻找到的定义，才是动态规划的本质。

文艺的说，动态规划是寻找一种对问题的观察角度，让问题能够以递推（或者说分治）的方式去解决。寻找看问题的角度，才是动态规划中最耀眼的宝石！

附加例子

为什么需要dp[i] + 1 > dp[k]? lis([1,3,6,7,9,4,10,5,6])在处理10的时候，不应该由4来更新dp，也是应该由9所决定的dp来更新。

Reference

什么是动态规划？动态规划的意义是什么？