动态规划5部曲Leetcode题目
1.斐波那契数2.爬楼梯3.爬楼梯-最小花费4.不同路径4.不同路径||
动态规划5部曲确定dp数组以及下标的含义确定递推公式dp数组如何进行初始化，如dp[0]、dp[1]，以及边界条件确定遍历顺序举例推导dp数组 Leetcode题目 1.斐波那契数
斐波那契数
dp数组代表最后的数列和递推公式dp[n]=dp[n-1]+dp[n-2]初始化dp[0]=0,dp[1]=1,遍历顺序从左向右遍历，for循环从i=2开始声明数组dp长度为n+1大小，最后返回dp[n]
注：声明数组长度为n+1是因为数组索引是从0开始的，要想返回dp[n]，必须要声明n+1长度的数组。
class Solution {
public:
int fib(int n) {
if(n<=1){
return n;
}
vectordp(n+1,0);
dp[0]=0;
dp[1]=1;
for(int i=2;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
};
2.爬楼梯
dp代表有多少中方法爬到楼顶递推公式dp[n]=dp[n-1]+dp[n-2]初始化这时不要使用dp[0]了，容易混淆概念，先初始化一个长度为n+1的数组dp(n+1,0),再初始化dp[1]=1,dp[2]=2;for循环遍历从左到右，初始化int i=3,i<=n.
70. 爬楼梯
class Solution {
public:
int climbStairs(int n) {
if(n<=1){
return n;
}
vectordp(n+1,0);
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
};
3.爬楼梯-最小花费
746. 使用最小花费爬楼梯
dp下标含义为最小花费递推公式为dp[i]=min(dp[i-1],dp[i-2])+cost[i];注意这里是比较dp[i-1]和dp[i-2]之间最小值再加上cost[i]初始化dp[0]=cost[0],dp[1]=cost[1]，声明数组dp大小为n最后返回return min(dp[n-1],dp[n-2]);为什么要比较n-1和n-2位置呢
以cost=[10,15,20]为例:
dp[0]=10 dp[1]=15 dp[2]=min(dp[0],dp[1])+cost[2]=30,此时等于30这不是最小花费，最小花费是要将n-1和n-2处花费进行比较
class Solution {
public:
int minCostClimbingStairs(vector& cost) {
int n=cost.size();
vectordp(n);
dp[0]=cost[0];
dp[1]=cost[1];
for(int i=2;i
4.不同路径
dp数组代表路径数递推公式dp[m][n]=dp[m-1][n]+dp[m][n-1]初始化由于左边一列和上边一行都只有一条路径才能到达，因此全部初始化为1
注：二维数组初始化vecordp(m,vector(n,0))
class Solution {
public:
int uniquePaths(int m, int n) {
vector>dp(m,vector(n,0));
for(int i=0;i
4.不同路径||
dp数组下标代表路径数递推公式dp[m][n]=dp[m-1][n]+dp[m][n-1]这道题主要考虑遇到障碍怎么处理？
初始化时如果遇到障碍怎么处理？障碍值为1，如果grid值为1你那么立即终止循环，后面的路径数应该都为0.
比如初始化列我给出两段代码：
遇到grid值为1初始化为0，值为0初始化为1
for(int j=0;j
在循环体判断条件加上如果grid值为0才给与初始化，否则直接退出循环，这才是正确的代码，因为如果遇到障碍1后面的路都不通了，路径数就到此为止了。
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++){
dp[0][j] = 1;
}
双层for循环代码细节：遇到障碍为1时直接continue下一次循环。
class Solution {
public:
int uniquePathsWithObstacles(vector>& obstacleGrid) {
int m=obstacleGrid.size();
int n=obstacleGrid[0].size();
vector>dp(m,vector(n,0));
for(int i=0;i
