新手福音：用六道题教新手快速入门动态规划算法基础题

 

        算法初学者们在见到动态规划题时，总会心生莫名的压力，认为这玩意又怪又难搞，虽然我们都知道这玩意能很明显地提高效率，但总是觉得无从下手，甚至连题目都看不懂，我也曾经是这样，但我在B站看到了九章算法侯老师的动规公开课，大受震撼，豁然开朗。今天我就用六道题，根据侯老师的思路，带你快速入手动态规划基础题，用通俗易懂的方法，告别各种难以理解的名词和以往无从下手的尴尬。

什么是动态规划？

        动态规划(Dynamic Programming)，简称动规或DP。通俗地说，动规就是用空间来换时间，这类问题基本上都需要开一个数组，用来存储某些对问题解决起关键作用的数据，减少了某些问题大量的重复计算过程，从而达到提升效率的目的。

如何分析动规问题？

        动规题最大的特性就是可以将一个母问题通过某种关系转换成子问题，这也是动规题的重点，找到这种变换关系，问题便可迎刃而解。

        有的问题也许比较难找到这种变换关系，故我们可以从完成题目问题的最后一步入手，找到这最后一步，并稍加观察，也许就能得到这种变换关系了。

        这样说不好理解，来看一道题：

 路径的数目（来源：LeetCode）：

        剑指 Offer II 098. 路径的数目

        一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

        机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

        问总共有多少条不同的路径？

        根据题给条件，机器人只能向右或向下走，故我们可以发现，要想到达最右下角格子，必须先要到达其左边或上边的格子。我们便可以得到解决该问题的最后一步：走到最右下角格子的左边或上边的格子。根据加法原理可得，走到最右下角格子的路径数量是：走到其左边格子的路径数量与走到其上边格子的路径数量的和。我们用一个数组来表示移动到坐标为(i,j)格子的所有路径的数量，便可得到这样一个关系式：

        

        这样的关系式正是动规题中大名鼎鼎举足轻重的状态转移方程。

        找到母问题与子问题关系后便可以根据题目特定条件来初始化某些特定的值。在本题中我们可以发现，机器人若要走到第一行或第一列的任意一点，都只有一种路径，即一直往下走或一直往右走。我们就可以将数组进行初始化，即i为0或j为0时f[i][j]的值为1。

        再按照逐行从左往右的顺序遍历并求解该数组，便可得到数组每一项的值。但为什么是逐行从左往右的顺序呢？我们应该知道，要求解(i,j)的值，就要知道(i-1,j)和(i,j-1)的值，这就意味着求解点的值是建立在另外两个求解过的点的值上的，所以这两个求结果的点应当先于待求结果被求解。

        代码实现如下：

int uniquePaths(int m, int n) 
{vector<vector<int>> f(m,vector<int>(n));//vector是一种可以看做数组的容器对象//此处用vector的vector来表示二维数组for(int i = 0 ; i < m ; i ++){for(int j = 0 ; j < n ; j ++){if(i == 0 || j == 0)f[i][j] = 1;elsef[i][j] = f[i - 1][j] + f[i][j - 1];}}return f[m - 1][n - 1];
}

        当然，动规不止有这一种题目，根据题型分类，有计数型、可行性型、最值型三种类型的题目，上一题属于计数型。接下来再讲讲另外两个题型的经典例题。

        可行性型：

跳跃游戏（来源：LintCode）：

        116 · 跳跃游戏

        给出一个长度为n的非负整数数组，你最初定位在数组的第一个位置。

        数组中的每个元素代表你在那个位置可以跳跃的最大长度。

        判断你是否能到达数组的最后一个位置。

        首先我们要找到最后一步，最后一步便是假设现在处在第i个位置，并且数组中的第i个元素值加上i可以达到数组最后一个元素的下标索引。即a[i] + i >= n，我们便可以得到该问题的子问题：能否跳到第i个位置。

        稍加分析，我们若想要跳到第i位上，那必须要能跳到该位置之前某个满足a[j] + j >= i的位置上，而这就需要遍历第i位以前的每一位，只要找到一个满足条件的位置，第i位便可到达。用数组元素f[i]来表示能否到达第i位。我们根据这个关系可以得到母问题与子问题的关系式：

        

        该式含义为：[0,i)中的任一数，只要满足第j位可到达（值为true），并且第j位对应元素与j的和大于等于i，即可到达第i位，也即f[i]值为true。

        找到关系后我们可以确定初始条件，因为题目所给起点为0，故f[0]值为true。

        确定初始条件后我们应确定计算顺序，因为要判断第j位能否到达需要知道j之前的位数能否到达。

        代码实现如下：

bool canJump(vector<int> &A) 
{int n = A.size();vector<bool> f(n,false);f[0] = true;for(int i = 1 ; i < n ; i ++){for(int j = 0 ; j < i ; j ++){if(f[j] &&A[j] + j >= i){f[i] = true;break;}}}return f[n - 1];
}

        接下来是第三类题型，最值型：

换硬币（来源：LintCode）：

        669 · 换硬币

        给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1.

        首先我们找到最后一步：要用最少的硬币凑出n元，就应当先找到凑出n-m（m为所有可能的面值）元的最少硬币，再加上最后凑上的那枚硬币。便可得到子问题：求出凑出n-m元的最少硬币数量。用f[i]来表示i元能否通过已有的硬币面值凑出。

        我们可以推出母问题与子问题的关系式：

        

        该式中a,b,c,...,s为所有可能的面值，用m统称，要凑出i元，就要凑出i-m元，并且由于他们相差一枚硬币，故凑出i元所需硬币数量为凑出i-m元的硬币数量+1。

        找到关系式后我们确定初始条件，0元需要0枚硬币凑出，故f[0]值为0。之后将所有值先赋值为INT_MAX，因为有的金额可能凑不出来，比如题目给我2元和3元面值的硬币，但要凑出1元，显然不能凑出，故应当为INT_MAX。最后若待求面值对应的硬币数量为INT_MAX，则应当返回-1，因为这是题目要求的。

        最后确定计算顺序，由于要求f[i]，就应先求f[i-1]...f[i-s]等，故应当从左往右计算。

        代码实现如下：

int coinChange(vector<int> &coins, int amount) 
{vector<int> f(amount + 1);int n = coins.size();f[0] = 0;for(int i = 1 ; i < amount + 1 ; i ++)//循环应当从1开始，如果从0开始会覆盖掉f[0]{f[i] = INT_MAX;for(int j = 0 ; j < n ; j ++){if(i >= coins[j] && f[i - coins[j]] != INT_MAX){f[i] = min(f[i - coins[j]] + 1, f[i]);}}}if(f[amount] == INT_MAX){return -1;}return f[amount];
}

小结一下：

        动态规划题有四个基本步骤：

        一、确定状态，这其中包括了最后一步与子问题的寻找。

        二、确定状态转移方程，这反映了母问题与子问题的关系，是解题的关键。

        三、初始化与边界条件，某些值求不出来，但又是解题所必须要的条件，此时就应当手动赋值初始化，边界条件不是每一题都需要，第一题中需要边界条件，即第1行和第1列的所有点的路径数量都为1，如果按照f[i][j] = f[i - 1][j] + f[i][j - 1]的规律计算的话将会数组越界。但第二题中不需要设置边界条件，因为其不会越界。

        四、确定计算顺序。

        根据以上四个步骤，基本就可以解出较为简单的动规题。而至于在动规中开辅助数组需要开几维，取决于母问题和子问题中有多少个变量，有几个变量就开几维。如机器人路径中，有i,j两个变量，辅助数组就是二维数组，而换硬币中，只有i这一个变量（a,b,c,...,s为常亮），故只需开一维数组。

        接下来我们根据这四个步骤来看一看下面的三道我在LeetCode上做过的题（难度较易）。

我做过的部分动规题

一、斐波那契数列（来源：LeetCode）：

        剑指 Offer 10- I. 斐波那契数列

        写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

        F(0) = 0,   F(1) = 1
        F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
        斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

        答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

        首先找最后一步：

        根据题意，要解出第n项，就应解出第n-1和第n-2项。

        接下来是子问题：

        可以转化为求第i个斐波那契数。

        再接下来是状态转移方程：

        题目已经给出：F(N) = F(N - 1) + F(N - 2)

        初始值与边界条件：

        初始值题目也已经给出，F(0) = 0,   F(1) = 1。本题不会越界，故不需要考虑边界条件。

        计算顺序：

        因为计算第i项需要第i-1和第i-2项，所以应当从左向右计算。

        代码实现：

    int fib(int n) {vector<int> ans(n + 1,1);ans[0] = 0;for(int i = 2 ; i < n + 1 ; i ++){ans[i] = (ans[i - 1] + ans[i - 2]) % 1000000007;}return ans[n];}

        代码优化：

        由于我们每次只需要当前项的前两项，故可以只用两个变量来表示当前项的前两项，再用一个变量来表示当前要求的项，每次循环时在像车轮一样轮换位置，从而只需要常数级别的空间开销，达到优化的效果。

    int fib(int n) {int a = 0;int b = 1;int c;for(int i = 0 ; i < n ; i ++){c = (a + b) % 1000000007;a = b;b = c;}return a;}

二、礼物的最大价值（来源：LeetCode）：

        剑指 Offer 47. 礼物的最大价值

        在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

        这道题和机器人路径问题蛮像的，思路也是类似，唯一不同就是该题要求最大数量，属于最值性问题，机器人路径属于计数型问题。

        找最后一步：

        要到达右下角，必须先到达右下角左边或右下角上边相邻的格子，故走到右下角能得到的最大值为走到这两个格子所能拿到的最大值与右下角的值的和。

        子问题：

        求走到(i,j)格所能拿到的最大价值。

        状态转移方程：

        

        f[i][j]表示走到(i,j)格所能拿到的最大价值的礼物，a[i][j]表示(i,j)格的礼物价值。

        初始值和边界条件：

        初始值：f[0][0] = a[0][0]

        边界条件：f[0][j] = f[0][j - 1] + a[0][j]，f[i][0] = f[i - 1][0] + a[i][0]，即第一行每格所能拿到的最大价值的礼物是其左边格子能拿到得到最大价值的礼物加上其格子中的值，第一列每格所能拿到的最大价值的礼物是其上边格子能拿到的最大价值的礼物加上其格子中的值。

        计算顺序：

        与机器人路径问题一样，逐行从左到右计算。

        代码实现：

    int maxValue(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();int maxi = grid[0][0];vector<vector<int>> ans(m,vector<int>(n,0));ans[0][0] = grid[0][0];for(int i = 0 ; i < m ; i ++){for(int j = 0 ; j < n ; j ++){if(i == 0 || j == 0){if(i == 0 && j == 0)continue;if(i == 0)ans[i][j] = ans[i][j - 1] + grid[i][j];if(j == 0)ans[i][j] = ans[i - 1][j] + grid[i][j];}elseans[i][j] = max(ans[i - 1][j], ans[i][j - 1]) + grid[i][j];if(maxi < ans[i][j])maxi = ans[i][j];}}return maxi;}

        代码优化：

        由于循环中每一次判断i,j是否为0会造成冗余，故我们可以直接初始化赋值，以达到优化的目的。

    int maxValue(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();int maxi = grid[0][0];for(int i = 1 ; i < m ; i ++){grid[i][0] += grid[i - 1][0];if(maxi < grid[i][0])maxi = grid[i][0];}for(int i = 1 ; i < n ; i ++){grid[0][i] += grid[0][i - 1];if(maxi < grid[0][i])maxi = grid[0][i];}for(int i = 1 ; i < m ; i ++){for(int j = 1 ; j < n ; j ++){grid[i][j] += max(grid[i - 1][j], grid[i][j - 1]);if(maxi < grid[i][j])maxi = grid[i][j];}}return maxi;}

三、把数字翻译成字符串（来源：LeetCode）：

        剑指 Offer 46. 把数字翻译成字符串

        给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

        最后一步：

        要翻译长度为n的数字，就应翻译其前n-1位和其前n-2位。

        子问题：

        翻译长度为i的数字。

        状态转移方程：

        若其最右边两位为10到25之间的数，由于这些数字也可以进行翻译，故原数字的翻译方法就为其前n-1位和其前n-2位的和。

        故状态转移方程为：

        若最右边的两位数组成10到25之间的数，状态转移方程为：

        否则状态转移方程为：

        初始值和边界条件：

        初始值：f[0] = f[1] = 1，即没有数字和有一位数字都只能有一种翻译方法（翻译成空串或该翻译成只含有数字对应的字母的字符串）。

        边界条件：无。

        计算顺序：

        因为求第i项会需要第i-1项或第i-1项和第i-2项，故顺序为从左到右。

        代码实现：

    int translateNum(int num) {string s = to_string(num);vector<int> dp(s.size() + 1,0);dp[0] = 1;dp[1] = 1;for(int i = 2 ; i < s.size() + 1 ; i ++){dp[i] += dp[i - 1];if(s[i - 2] != '0' && ((s[i - 2] - '0')*10 + (s[i - 1] - '0')) < 26)//用来判断最后两位是否属于10-25之间{dp[i] += dp[i - 2];}}return dp[s.size()];}

总结：

        经过这六道题，你应该也记住了动规题的基本解题模式遵循以上的几个步骤，相信你跟着思路看了看这些题目会感觉自己行了，去试一试吧，在LeetCode上刷个几十题动规，基本就没啥大问题了，大部分的动规题都能游刃有余了，当然，特别难的题还是需要时间来琢磨琢磨的。

        最后，建议大家去看看B站九章算法侯老师讲的动规公开课，非常清晰，我看了是受益匪浅，本文很多思路也是来源于该视频。

        【动态规划专题班】ACM总冠军、清华+斯坦福大神带你入门动态规划算法