五大算法之动态规划套路详解（1）

前言：

一、Why?为什么需要动态规划

二、What？什么是动态规划

三、How？如何利用动态规划做题

四、思路总结

前言：

     对于很多学习算法的同学来说，往往是跟着老师和学校教材上课，然后去刷题练熟练度；或者从网上的文章中寻求套路。对于这两个选择，我觉得都挺好，但是如果从0开始去接触这些算法思想，我总是想问why?waht?how?，然后利用这个寻求到的套路过关斩将（主要是斩杀面试题），去刷LeetCode。希望文章会对刚刚接触的你或已入题海的你有帮助，我也会不断改进，毕竟我也是一只菜猫。文章借鉴到的资料都会列出出处，可以直接去查看其它相关文章（本次主要采用C++代码，后面的解题文章两种代码都会给出C++/JAVA）。

一、Why?为什么需要动态规划

     如果我问为什么1+1=2是正确的，可能你不能很系统的回答我，或者直接怼我一句。但“为什么需要动态规划”这个问题倒是有答案的,首先我们从解题角度来看，给出最简单的例子：

     题目要求斐波那契数列Fib(n)的值？

     在学习递归的课堂上，这个例子总是会被拿出来鞭尸，我们总是知道Fib(n) = Fib(n-1) + Fib(n-2)，于是你可以很快的写出如下的代码：

int Fib(int n)
{
    if(n==1||n==2) return 1;
    return Fib(n-1) + Fib(n-2);
}
           

     如果你可以很快写出这个式子，那么递归已经进入门槛了，其中Fib(7)=13，我们可以画一个随意的递归树查看我们递归的过程：

     你可能会很开心的提交这个程序，然后输入7之后得到13，非常的开心，可是当你输入40的时候，等待总是漫长的（要注意精度问题），等了十几秒钟之后，你可能会不耐烦的关掉程序窗口。这个时候，你仔细的看看递归树，就会发现算法的时间复杂度竟然是O(2^n)指数级别的，你就想到需要更快的算法来帮助你。

     那么问题的关键在于自顶向下的过程中，总是会重复的计算很多子问题，例如我们的F(5）就重复进行运算，那么我们就要想办法不在重复的计算这些值。你可能会想到备忘录的方法，定义一个数组，去保存已经计算过的值，这样就可以减少重复计算子问题，从而我们只需要计算出n个值即可，计算的数量就从2^n降低到n，完全是降维打击。例如下面的代码：

int Fib(int n) {
	if(n<1) return 0;
	//初始化备忘录 
	vector<int>memo(n+1,0);
	return helper(memo,n);
}

long helper(vector<int>&memo,int n) {
	if(n==1||n==2) return 1;
	if(memo[n] != 0) return memo[n];//有值的话直接使用
	memo[n] = helper(memo,n-1) + helper(memo,n-2);//存储新的值进入数组
	return memo[n];  
}
           

     这样当你再次输入40的时候，一下就出来了结果（不同的编程语言代码实现不一样，但是思想却是一样的；这里C++可能用vector，在java中可能就是hashmap，所以不必在意是哪一种编程语言实现的代码）。而再一次计算时间复杂度，我们发现，的确是O(n)级别。

     对于这样有重复子问题的题目，我们在这里使用递归，然后使用备忘录的方式进行优化的确没有问题。可是我们都知道，整个问题我们是自顶向下的方式进行的，可以返回递归树在看一眼题目。那如果是自顶向上呢，我们一步一个台阶的走，最后走到终点呢？动态规划正是自顶向上的方法，循环迭代就能得到答案，那么相比备忘录呢？我们可以直接看DP（动态规划）的代码：

int Fib(int n) {
	vector<int>dp(n+1,0);//dp数组
	dp[1] = dp[2] = 1;//初始状态
	for(int i=3;i<=n;i++) {//循环迭代自顶向上得到答案 
		dp[i] = dp[i-1] + dp[i-2];
	}
	return dp[n]; 
}
           

     相比于上面备忘录的代码，最直观的感觉就是代码量更少了，而且我们可以看到，不需要递归，直接循环迭代就可以得到结果，使用dp table来实现：

     整个代码的运算就是从f(1)开始不断迭代得到最后一个数字，其实我们仅仅用到了两个位子就能计算第三个，所以这个dp table还可以进行空间的优化（状态压缩：缩小dp table大小，只记录必要数据），像这样：

int Fib(int n) {
	if(n==1||n==2) return 1;
	//初始化状态 
	int prev = 0,curr = 1;//只需要两个位子就可以得到答案 
	for(int i=0;i<n-1;i++) {//不断向前移动就可以得到最后的答案
	//观察dp table就会发现除去初始化的值仅仅需要计算n-1次，所以这里迭代为n-1次 
		int sum = prev + curr;
		prev = curr;
		curr = sum;
	}
	return curr; 
}
           

     这样一看，时间复杂度和空间复杂度都及其优化了。所以看来动态规划解决这样的重复子问题还有一手，那么你知道为什么要用动态规划了么？

     如果从上面来看，你可能会回答我：“因为对于重复子问题比递归更方便使用，因为自顶向上的循环迭代比较符合思维”。我觉得你说的都对，可是我还想告诉你，除了重复子问题，动态规划其实解决的是拥有最优子结构的最值问题。比如，最长子序列问题、石子游戏啊这些。那么动态规划长啥样呢？可能从上面的例子你可以隐约看出一些东西，但是让我们更加系统的去了解它。

二、What？什么是动态规划

     首先引用维基百科的介绍：

     动态规划在寻找很多重叠子问题的情况的最佳解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并存储，从简单的问题知道整个问题都被解决。因此，动态规划存储递归时的结果，因而不会在解决同样的问题时花费时间。

     动态规划只能应用于有最佳子结构的问题。最佳子结构的意思是局部最佳解能决定全域最佳解（对于有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单来说，问题能够分解成子问题来解决。

     提炼出“重叠子问题”，“最佳子结构”这个概念出来，结合上面的例子，有那么一点理解什么样子的题目可以使用动态规划来做，可以使用自顶向上的循环迭代方法。但是什么是动态规划呢？

     这就需要我们理解“状态转移方程”的概念，或者我更愿意把它理解为高中数学中数列的通项公式（或者说函形似函数公式）。上面的斐波那契数列不正是这样吗？a(n）= a(n-1) + a(n-2)，然后我们要求n=7，我们往往会先要求出初始状态的值（比如a(0),a(1)），然后手动的计算往上推，就得到a(7)的值。这其中n-1状态和n-2状态相加转移才得到n的状态，所以称之为状态转移方程。

     所以，动态规划这里就理解为通过规划子状态得到最终状态的算法，它的特点为拥有重叠的子问题和最优子结构（即子结构互相独立）。利用f(ab)=f(a)*f(b)来理解就是要想f(ab)的值最大，那么a的值和b的值就要最大，不存在a增加而b减小的情况，a、b互相独立不制约。悄悄往上看斐波那契数列只是有着重叠子问题，而不存在最优子结构，所以严格来说不算动态规划，但是它作为入门却是一个经久不衰的例子。

     那接下来就让我们看符合以上两个点的题目，一起来看动态规划的具体套路（成为套路王---->很多套路都是备忘录、dp table，下面我们直接dp就好）。

三、How？如何利用动态规划做题

     首先给出我们的套路如下：

     所以，看题目之后确定可不可以用动态规划（是否有重叠子问题，是否有最优子结构），如果是，那么其实写出状态转移方程就已经完成了大半的题目了，所以我们先要写出状态转移方程：

1、确定 base case，这个很简单，从题目中就能够得到。

2、确定「状态」，也就是原问题和子问题中会变化的变量。

3、确定「选择」，也就是导致「状态」产生变化的行为。

4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。

     但这样给出一个套路就真的可以做题目了吗？其实这其中还是有很多细节，所以我们通过一个简单的例子来逐个分析，看看此套路是否可行：

《最长上升子序列》

     首先判断是不是可以使用动态规：“最优子结构，重叠子问题，后一状态取决于多个状态（具有选择）”。那么我们这一道题目要求的是最长上升子序列的长度，当前子序列长度是取决于之前的多个子序列的，子序列的选择不同，后面能够达到的长度也不一样（这也就是为什么我们要了解why,what，这样我们就很好判断是不是动态规划了）。

     所以当前状态取决于之前的多个状态（和选择有关系，并且互相独立），所以这里我们使用动态规划。

我们要写出状态转移方程，所以开始分析：

     仅仅读了题目之后定义dp[n]的含义，可能会有很多种（如果做得题目不是很多，可能没有办法一来就定义dp[n]，所以我们一点点分析）（以下我将递增子序列简称子序列）。

1、题目的【初始情况】也就是子序列长度：要么nmus.size()==0即长度为0，要么nums.size()==1即长度为1。

2、确定【状态】，也就是原问题和子问题中变化量。这里我们可以看到变化的是长度。

3、确定【选择】，选择不同的子序列，则后面子序列的长度会发生变化

4、定义dp[i]，所以我们可以定义dp[i]为某一个子序列的长度，为了区别不同的子序列，我们可以重新定义dp[i]为以num[j]结尾的子序列的长度。那么dp[i]的长度不正等于nums[j]子序列长度或者nums[j]+1的长度吗？（j<i），也就是说当前状态就是上一个状态转移或者上一个状态+1转移得到的，也就是说：dp[i] = max(dp[i],dp[j]+1) (j<i)

我们详细的写出状态转移方程也就是：

方程：dp[i] = max( dp[i], dp[j]+1)  (for j in [0,i)

每轮计算新的dp[i]时遍历[0,i)：

*如果num[i]>nums[j]，那么当前数字可以接在前一个子序列之后，长度加一即是dp[i]=dp[j]+1;

*如果num[i]<=nums[j]，跳过；

返回值也就是max(dp[i])，也就是我们题目所要求的长度。

     那么在我们定义了dp[i]之后在看看初始化条件也就是除去特殊情况，dp[i]都为1，因为每一个数字都可以作为以自己结尾的长度为1的子序列。

所以我们的代码就有：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = (int)nums.size();//特殊情况
        if(n==0) return 0;
        int ans = 0;
        vector<int>dp(n,1);//全部初始化为1
        for(int i=0;i<n;i++) {
            for(int j=0;j<i;j++) {
                if(nums[i]>nums[j]) {
                    dp[i] = max(dp[i],dp[j]+1);
                }  
            }
             ans = max(dp[i],ans);
        }
        return ans;
    }
};
           

     当然，仅仅一两个简单的题目不可能展示很多情况，所以我们现在的目的就是记住这个套路，然后不断的刷题。当然，我也会规划其它动态规划的套路（上面的题目还可以用贪心、二分查找，可以参考其他博客）。

四、思路总结

所以我们总结一下思路：

•  判断可不可以用动态规划去做（了解题目之后，从动态规划的特点入手：最优子结构、重叠子问题、状态转移），上面最长上升子序列我们就是这样判断的。
• 想办法写出状态转移方程

1. 确定 base case，这个很简单，从题目中就能够得到。
2. 确定「状态」，也就是原问题和子问题中会变化的变量。
3. 确定「选择」，也就是导致「状态」产生变化的行为。
4. 明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。

• 定义了dp[i]之后，写出状态转移方程（讨论各种情况）
• 编写代码（循环迭代，注意初始化）
• 尝试进行优化（也可以借鉴别人的优化，例如状态压缩，降低空间复杂度）

     后面还会继续更新套路的哦~

五、参考资料

1、最长上升子序列（动态规划+二分查找，清晰图解）

2、动态规划套路详解