【数据结构】动态规划-基础篇

针对动态规划问题，我总结了以下5步：

确定dp数组以及下标的含义；

递推公式；

dp数组如何初始化；

遍历顺序；

打印dp数组（用来debug）；

以上5步适用于任何动态规划问题，下面针对题目，我们来具体实践：

说明：本题代码均为力扣AC代码。

题目一：斐波那契数

class Solution {
public:int fib(int n) {//1.dp[i]表示第i个斐波那契数的值//2.递推公式 dp[i] = dp[i-1] + dp[i-2]//3.dp[0] = 0 dp[1] = 1//4.遍历顺序：本题从前到后遍历即可if(n == 0 || n == 1)return n;vector<int>dp(n+1);dp[0] = 0;dp[1] = 1;for(int i = 2;i <= n;++i){dp[i] = dp[i-1] + dp[i-2];}return dp[n];//返回第n个斐波那契数的值}
};

当然，本题非常简单，不使用动态规划也是OK的。

class Solution {
public:int fib(int n) {//迭代if(n == 0 || n== 1)return n;vector<int>f(n+1);f[0] = 0;f[1] = 1;int cur = 0;for(int i = 2;i <= n;++i){cur = f[0] + f[1];f[0] = f[1];f[1] = cur;}return cur;}
};

 题目二：爬楼梯

分析一波：为啥递推公式是dp[i] = dp[i-1]+dp[i-2]？dp[i]为到达第i阶有dp[i]种方法，.dp[i-1]为到达第i-1阶有dp[i-1]种方法，.dp[i-2]为到达第i-2阶有dp[i-2]种方法，要想到达第i阶，只需从第i-1阶爬一阶或者从第i-2阶爬二阶即可，所以dp[i] = dp[i-1]+dp[i-2]。

class Solution {
public:int climbStairs(int n) {//1.dp[i]为到达第i阶有dp[i]种方法//2.递推公式：dp[i] = dp[i-1]+dp[i-2]//3.dp[1] = 1,dp[2] = 2//遍历顺序：因为dp[i]依赖于dp[i-1]、dp[i-2]，所以应该从前到后遍历vector<int> dp(n + 1);if(n == 1 || n == 2)return n;dp[1] = 1;dp[2] = 2;for(int i=3;i<=n;++i){dp[i] = dp[i-1]+dp[i-2];}return dp[n];//爬到第n阶一共有多少种方法}
};

题目三： 使用最小花费爬楼梯

分析一波：本题和上一道爬楼梯很相似，不过是加上了个花费，这里dp[i]为到达i阶楼梯最小的花费，要想到达第i阶，只需从第i-1阶爬一阶或者从第i-2阶爬二阶即可，从第i-1阶爬到第i阶需要花费dp[i-1]+cost[i-1],从第i-2阶爬到第i阶需要花费dp[i-2]+cost[i-2],本题要求最小花费，所以状态转移方程为dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]).

对于初始化，本题说了可以选择从下标为0或1的元素作为初始阶梯，还要注意一点是不跳不花费体力，所以dp[0] = 0,dp[1] = 0.

对于遍历顺序，由于dp[i]是依靠dp[i-1]和dp[i-2]推导的，所以遍历顺序是从前到后。

分析完以后，就能很丝滑的做出来啦！

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int>dp(n+1);dp[0] = 0;dp[1] = 0;for(int i=2;i<=n;++i){dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[n];}
};

题目四：不同路径

分析一波：本题是二维矩阵，所以dp数组应该定义成二维的，dp[i][j]代表从(0,0)位置走到(i,j)位置有多少种不同的路径，可以看到，如果想到达(i,j)的位置，只能从(i,j-1)的位置走一步或者从(i-1,j)的位置向下走一步，所以dp[i][j] = dp[i][j-1]+dp[i-1][j].

对于初始化，要想到达(i,j)的位置，要么从上面过来，要么从左边过来，所以我们要把最左边和最上边都初始化，初始化成多少呢？本题要求只能向右或者向下走，所以最上面行从最左侧走到最右侧只有一种走法，最左侧的列中从最上到最下也只有一种走法，所以初始化如下图。

class Solution {
public:int uniquePaths(int m, int n) {//创建m行n列的二维数组vector<vector<int>>dp(m,vector<int>(n));for(int i=0;i<m;++i)dp[i][0] = 1;for(int j=0;j<n;++j)dp[0][j] = 1;for(int i=1;i<m;++i){for(int j=1;j<n;++j){dp[i][j] = dp[i][j-1]+dp[i-1][j];}}return dp[m-1][n-1];}
};

题目五：不同路径II

本题和上一题类似，只是本题多了一个障碍物，对于状态转移方程，如果(i,j)位置有障碍的话，那么我们无法继续推导，所以我们需要添加一个条件就是当(i,j)位置不是障碍物时，我们进行推导，否则不去推导。对于初始化，和上一题不同的是，第一列如果有障碍物的话，障碍物后面的位置都无法到达，第一行也是如此，所以我们在初始化时应该加上一个条件，就是当前位置没有障碍物，我们才给dp[i][0]、dp[0][j]初始化成1.

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1)return 0;//创建m行n列的二维数组vector<vector<int>>dp(m,vector<int>(n));//dp数组初始化for(int i = 0;i < m && obstacleGrid[i][0] == 0;++i)dp[i][0] = 1;for(int j = 0;j < n && obstacleGrid[0][j] == 0;++j)dp[0][j] = 1;for(int i = 1;i < m;++i){for(int j = 1;j < n;j++){if(!obstacleGrid[i][j])dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
};

题目六：整数拆分

1.确定dp数组含义：dp[i]表示将i进行拆分后得到最大的乘积

2.确定递推公式：将i拆分成两个数最大积为j*(i-j)，拆分成三个及以上为j*dp[i-j]，这里有个问题，为什么j不拆？实际上，在我们拆分 dp[i-j] 过程中已经包含了拆分 j 的情况，所以这里只考虑如何对 i-j 进行拆分即可，所以递推公式为dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]))

3.dp数组如何初始化？根据dp数组含义，dp[0] = 0,dp[1] = 0,dp[2] = 1

4.遍历顺序：根据递推公式可以看出，dp[i]的状态依靠dp[i-j]的状态，所以是从前到后遍历。

class Solution {
public:int integerBreak(int n) {if(n == 0 || n == 1)return 0;if(n == 2)return 1;vector<int>dp(n+1);dp[0] = 0,dp[1] = 0,dp[2] = 1;for(int i=3;i<=n;++i){for(int j = 1;j<i;++j){dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]));}}return dp[n];}
};

对于本题，可以做一个小小的优化。对于拆分i使之乘积最大，一定是拆分成m个近似相同的子数才能得到最大乘积。只不过m我们不知道是几，但是可以确定的是m一定大于等于2，所以在判断条件中，只需要 j <= i/2 即可。举个例子，拆分10的话，可以拆分成5*5，也可以拆分成3*3*4，如果拆分成6*4，后续无论对4如何拆分都不可能得到最大的，因为我们要把i拆分成近似相同的子数才能得到最大值。

题目七：

1.明确dp数组及下标含义：1到i为节点的二叉搜索树的个数为dp[i]

2.递推公式：根据图中分析，dp[3]就是以元素1为头结点BST的数量+以元素2为头结点BST的数量+以元素3为头结点BST的数量，我们要计算dp[i],只需要让 j 从遍历 1 到 i，计算 j 为头结点对应BST的个数并将他们相加即可。注意，j为头结点时，其左子树数目为 j-1 个，右子树数目为 i-j 个状态转移方程：dp[i] += dp[j-1]*dp[i-j].

3.如何初始化？dp[0] = 1,因为空BST也是BST

4.遍历顺序：从前到后

class Solution {
public:int numTrees(int n) {if(n == 1)return 1;vector<int>dp(n+1);dp[0] = 1;for(int i=1;i<=n;++i){for(int j=1;j<=i;++j){dp[i] += dp[j-1]*dp[i-j];}}return dp[n];}
};