动态规划的本质,是对问题状态的定义和状态转移方程的定义。
引自维基百科
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\),
设\(F_k\)为:以数列中第\(k\)项结尾的最长递增子序列的长度.
求\(F_1, ..., F_N\)中的最大值.
显然,这个新问题与原问题等价。
而对于\(F_k\)来讲,\(F_1, ..., F_{k-1}\)都是\(F_k\)的子问题:因为以第\(k\)项结尾的最长递增子序列(下称LIS),包含着以第\(1, ..., k-1\)中某项结尾的LIS。
上述的新问题\(F_k\)也可以叫做状态,定义中的“\(F_k\)为数列中第\(k\)项结尾的LIS的长度”,就叫做对状态的定义。
之所以把\(F_k\)做“状态”而不是“问题” ,一是因为避免跟原问题中“问题”混淆,二是因为这个新问题是数学化定义的。
什么是状态转移方程?
上述状态定义好之后,状态和状态之间的关系式,就叫做状态转移方程。
比如,对于LIS问题,我们的第一种定义:
设\(F_k\)为:以数列中第\(k\)项结尾的最长递增子序列的长度.
设\(A\)为题中数列,状态转移方程为:
\(F_1 = 1\)(根据状态定义导出边界情况)
$F_k = max(F_{i} + 1 | A_{k} > A_{i}, i \in (1, ..., k-1)), (k > 1) $
用文字解释一下是:以第\(k\)项结尾的LIS的长度是:保证第\(i\)项比第\(k\)项小的情况下,以第\(i\)项结尾的LIS长度加一的最大值,取遍\(i\)的所有值(\(i\)小于\(k\))。
这里可以看出,这里的状态转移方程,就是定义了问题和子问题之间的关系。
可以看出,状态转移方程就是带有条件的递推式。
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 <k
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\)或者\(k\)的值,这是"无后效性"的通俗上的数学定义,符合这种定义的状态定义,我们可以说它具有“最优子结构”的性质,在动态规划中我们要做的,就是找到这种“最优子结构”。
在对状态和状态转移方程的定义过程中,满足“最优子结构”是一个隐含的条件(否则根本定义不出来)。
需要注意的是,一个问题可能有多种不同的状态定义和状态转移方程定义,存在一个有后效性的定义,不代表该问题不适用动态规划。这也是其他几个答案中出现的逻辑误区:
动态规划方法要寻找符合“最优子结构“的状态和状态转移方程的定义,在找到之后,这个问题就可以以“记忆化地求解递推式”的方法来解决。而寻找到的定义,才是动态规划的本质。
文艺的说,动态规划是寻找一种对问题的观察角度,让问题能够以递推(或者说分治)的方式去解决。寻找看问题的角度,才是动态规划中最耀眼的宝石!
附加例子
为什么需要dp[i] + 1 > dp[k]
? lis([1,3,6,7,9,4,10,5,6])
在处理10的时候,不应该由4来更新dp,也是应该由9所决定的dp来更新。