旅游区网站开发,企业网站建设的目标,app设计欣赏,学校网站定位针对动态规划问题#xff0c;我总结了以下5步#xff1a; 确定dp数组以及下标的含义#xff1b; 递推公式#xff1b; dp数组如何初始化#xff1b; 遍历顺序#xff1b; 打印dp数组#xff08;用来debug#xff09;#xff1b; 以上5步适用于任何动态规划问题#x…针对动态规划问题我总结了以下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;vectorintdp(n1);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;vectorintf(n1);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]所以应该从前到后遍历vectorint dp(n 1);if(n 1 || n 2)return n;dp[1] 1;dp[2] 2;for(int i3;in;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(vectorint cost) {int n cost.size();vectorintdp(n1);dp[0] 0;dp[1] 0;for(int i2;in;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列的二维数组vectorvectorintdp(m,vectorint(n));for(int i0;im;i)dp[i][0] 1;for(int j0;jn;j)dp[0][j] 1;for(int i1;im;i){for(int j1;jn;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(vectorvectorint 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列的二维数组vectorvectorintdp(m,vectorint(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;vectorintdp(n1);dp[0] 0,dp[1] 0,dp[2] 1;for(int i3;in;i){for(int j 1;ji;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;vectorintdp(n1);dp[0] 1;for(int i1;in;i){for(int j1;ji;j){dp[i] dp[j-1]*dp[i-j];}}return dp[n];}
};
