原理

性质

能采用动态规划求解的问题一般要具有3个性质：

• 最优性原理：如果问题的最优解所包含的子问题也是最优的，就称该问题具有最优子结构，即满足最优性原理。
• 无后效性，某个阶段状态一旦确定，就不受这个状态以后决策的影响。
• 有重叠子问题：即子问题之间不是独立的，一个子问题在下一阶段决策中可能被多次使用到。

关键

子问题

**子问题不一定是大问题的缩小版，关键点在于满足最优子结构。**例如：最大连续子序列问题

原问题f(n)是指在n个整数a[1…n]的序列中求出最大连续子序列的和（子序列可为空）。
子问题g(i)定义为，a[1…i]的最大右端子序列a[j…i]的和。
子问题有如下状态转移方程
$g(0)=0$g(0)=0$g(i)=max(g(i-1)+a[i], a[i])$g(i)=max(g(i−1)+a[i],a[i])
且，$f(n)=max(g(1), g(2)... , g(n))$f(n)=max(g(1),g(2)...,g(n)), 所以父问题可以通过求解子问题得出，父问题的最优解所包含的子问题也是最优的。

动态规划数组

动态规划数组的目的：

• 保存子问题的解，以求解父问题
• 某些情况下用于回溯寻找具体方案

如下面LCS问题的动态规划数组：

滚动数组
只保存相关的子问题的数据，以此来压缩空间。

状态转移方程

也就是大问题如何转移成小问题的。
如求最大公共子序列LCS

有两个序列X[0…n-1]，Y[0…m-1]， 用dp[i][j]表示X[0…i0-1], Y[0…j-1]的最大公共子序列长度。有：
$dp[i][j]=0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i=0 ||j=0$dp[i][j]=0                                                         i=0∣∣j=0$dp[i][j]=dp[i-1][j-1]+1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ a[i-1]=b[j-1]$dp[i][j]=dp[i−1][j−1]+1                   a[i−1]=b[j−1]$dp[i][j]=max(dp[i][j-1],dp[i-1][j] \ \ \ \ \ a[i-1]\neq b[j-1]$dp[i][j]=max(dp[i][j−1],dp[i−1][j]     a[i−1]​=b[j−1]

相当于是找递归定义。和递归的主要区别在于：

• 递归不会保存子问题的解，通常$f(n)=f(n-1)+...+f(n-k)$f(n)=f(n−1)+...+f(n−k),k是一个定值，意味着递归只利用有限个小问题的解。
• 而动态规划是根据需要保存小问题的解，也就是说可以$f(n) = f(n-1) +...+f(1)$f(n)=f(n−1)+...+f(1),
• 递归只能利用前面有限步的解。动态规划可以利用前面所有解，既可以顺序着用，也可以跳跃着用。比如dp[j] 使用dp[i-k]

实现思路

• 自底向上

• 自顶向下：类似于递归，但为了不重复计算，需要使用备忘录。