动态规划入门

**动态规划（英语：Dynamic programming，简称DP）**是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

——维基百科

观前提示：本文需要一定的算法基础，包括但不限于递推、搜索、回溯、递归。

如果说递归是算法学习面临的第一道门槛，那么动态规划就是第二道门槛。这两者的学习都有一个相似的特点——抽象。

下面这篇文章是笔者认为最好理解入门动态规划的路线与方式。

笔者虽然比较喜欢用Python，但是不可否认C在效率方面比Python快得多，且竞赛也大多使用C，因此本文代码也用C++写。

（不过如果学习了Python，应该也不难理解）

——————————————————————————掉头发的分割线————————————————————————

网上很多教程以01背包开始动态规划的第一堂课，笔者私以为这是不太合理的。

固然，开始学习动态规划时大家大多已经学会了DFS（深度优先搜索）和回溯法，01背包的最朴素的解法也是使用暴力法进行的，但是01背包的动态规划并不是最容易理解的动态规划。

本文从一维动态规划到二维动态规划带你入门动态规划。

一、动态规划思想

动态规划的核心思想是非常简单的：将一个大问题分解到多个子问题，当你获得每个子问题的最优解时，大问题也得到了最优解。

让我们先阅读这道题（别着急做）：

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：
1
2
3
4
5
6
7
8
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2：
1
2
输入：triangle = [[-10]]
输出：-10
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/IlPe0q
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

对于最朴素的算法，那么能想到的自然就是深度优先搜索。遍历每个节点，但是你会发现每个节点都出现了大量的重复运算。

在此附上暴力算法的dfs函数：

int a[100][100];//存储三角形数据
int dep;//三角形深度
int dfs(int x,int y){
    if (x<dep){
        return min( dfs(x+1,y), dfs(x+1,y+1) ) + a[x][y] //取第[x+1][y]个位置的三角形和第[x+1][y+1]个三角形的路径的最小值。
    }
    else {
        return a[x][y];// 如果到达递归边界也就是三角形的最底层，那么就直接返回数值。
    }
}

为什么会超时呢？答案很简单，因为我们重复计算了。每个顶点左下和右下是想象的两个三角形，这两个三角形有重叠。时间复杂度在O(2^n)，显然对于超过25左右的数据，运算量就已经破3000万，显然不可取。

那么下来我们就要引入神器动态规划了：

动态规划有两个非常重要的概念：状态与状态转移。

顾名思义：“状态”即为当前你这一步你的状态。在这个例子中即为你当前的路径之和。

“状态转移”即为你要达到这一步的状态时需要从上一个状态的转移的过程。

在这个例子中，当你位于第i层第j个三角形时，

定义dp[i][j]即为你从顶端到达这个三角形的最短路径。

数组a[i][j]为当前这个位置的数值。

由于你到达这个节点，只能从上层的j位置或j-1位置来，那么可得动态转移方程：

1	dp[i][j] = min( dp[i-1][j] + a[i-1][j], dp[i-1][j-1] + a[i-1][j-1] ) + a[i][j]

可见，你只需要一个二重循环就能解决这个问题：

for(int i=0;i<=dep+1;i++){
    for(int j=0;j<=dep+1;j++){
        dp[i][j]=INT_MAX;
    }
}				//将dp数组设定为最大值，相当于隐性设定了边界，当然你也可以在下面判定边界。
dp[1][1]=a[1][1];
for (int i=2;i<=dep;i++){
    for (int j=1;j<=i;j++){
        dp[i][j] = min( dp[i-1][j] + a[i-1][j], dp[i-1][j-1] + a[i-1][j-1] ) + a[i][j];//动态转移方程
    }
}

可以看到时间复杂度仅为 $O(n^2)$ ，比起 $O(2^n)$ 要快很多，但是你也同时会发现空间复杂度也会高很多。因此动态规划也被称为“用空间换时间”。

二、一维DP

如果说上一道题目可能会让你以为动态规划或许就是贪心的变种。但是实际上，动态规划是一种很严谨的数学方法。

所谓一维DP，就是最简单的一种动态规划。下面这道题目就是最经典的动态规划入门题：

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：
1
2
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：
1
2
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
1
2
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

同样，既然是动态规划的题目，那么就有两个关键的需要考虑的方面：

状态：当你考虑到第i个节点时，那么它的前继节点必定是前i-1个节点中的一个，同时对于后继节点也没有后效性。那么就可以利用动态规划了。

定义dp[i]为第i个节点的最长严格递增子序列的长度。

状态转移方程：对于第i个节点，由于它的前继节点必定是前i-1个节点中的一个，那么我们只要遍历前i-1个节点，如果第j个节点的大小比第i个节点小，那么就可以执行状态转移方程为：

1	dp[i] = max( dp[i] , dp[j] + 1)

TIPS：需要注意的是dp[i]要在遍历前初始化为1，因为可以事先假如自己就是这个最长严格递增子序列的第一个开头，那么长度就是1。

同样，也只需要简单的二重循环就可以解决这个问题：

memset(dp,0,sizeof(dp));
for (int i=1;i<=n;i++){
    dp[i]=1;
    for (int j=1;j<i;j++){
        if (a[i]>a[j]){
            dp[i]=max(dp[i],dp[j]+1);
        }
    }
}

最后你只需要遍历整个dp数组，找到最大的数值，那就是最长严格递增子序列的长度。

进阶：这个方法是最朴素的动态规划，时间复杂度为 $O(n^2)$ 。还能利用二分+动态规划把时间复杂度缩减为 $O(n log n)$ ，想想怎么解决呢？

三、二维DP

二维DP相当于状态中有两个参量，这是一种更加复杂的动态规划。

我们以一道最经典的**01背包问题（knapsack problem）**为例：

海王，可泡之女甚多，而精力有限，泡哪些才更加不枉此行？

给定海王的总精力为 $N$ ，女生总数为 $M$ ，泡每个女生的精力是$ t_i$ , 每个女生的颜值为 $a_i$ ，

问：海王在精力范围内，泡哪几个女生才能使得在颜值总和最高？

定义子问题 $P(i,W)$ ，在前 $i$ 个女生中挑选所需总精力不超过 $W$ 的人（当然每个女生只能选一次），使得总颜值最大；这时的最优值记作 $m(i,W)$ ，其中 $1 \le i\le M$ ， $1\le W \le N$ 。

考虑第 $i$ 个女生，无外乎两种可能：选，或者不选。

不选的话，剩余的精力不变，改变为问题 $P(i-1,W)$ ；
选的话，剩余的精力变小，改变为问题 $P(i-1,W-t_i)$ 。

通俗一点说 $P(i,W)$ 就是状态，定义dp[i][W]在前 $i$ 个女生中挑选所需总精力不超过 $W$ 的总颜值的最大值。那么动态转移方程就出来了：

1	dp[i][W] = max ( dp[i-1][W] , dp[i-1][W-t[i]] + a[i] )

这里提供一个输入输出样例：

输入：
70 3        //海王有70点精力，共有三个女生
71 100		//第1个女生需要71点精力，颜值是100
69 1		//第2个女生需要69点精力，颜值是1
1 2			//第3个女生需要1点精力，颜值是2

输出：
3			//海王只能泡到第2个和第3个女生，总颜值为3

同学看出这是哪里的样例么，嘿嘿嘿，懂得都懂。

这样动态规划同样只需要一个二重循环就可以解决了：

for (int i=1;i<=m;i++){				//从第一个女生开始
    for (int j=n;j>=0;j--){			//每个循环从剩余第n点精力开始
        if (j-t[i]>=0){				//判定是否装得下
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+a[i]);
        }
        else{
            dp[i][j]=dp[i-1][j];
        }
    }
}

那么最后答案在哪里呢，自然就在dp[m][]中，只需要最后遍历找到最大值就行了。

int ans = 0;
for (int i = 0; i <= n; i++)
{
   ans = max(ans, dp[m][i]);
}

四、总结

如果你很认真的看完了前面的所有内容，并且前面的几道经典题都可以独立自主完成后，可以恭喜你终于打开了计算机学中动态规划这个大类的大门。

当然前面的这几道题我所提供的都是动态规划的最朴素的解法。

对于最长严格递增子序列问题来说，时间复杂度为 $O(n^2)$ ，还有更好的优化方法通过二分法，能缩减到 $O(nlogn)$

对于0/1背包问题来说，空间复杂度为 $O(n^2)$ ，还有更好的优化方法进行状态压缩到 $O(n)$ 。

这些我都没有提到，网上这些教程都很多，希望读者也能自己去试一试。

总之，希望读者们在我这篇入门文章中有所收获。