leetcode-hot100-动态规划五步总纲-
目录
leetcode hot100–动态规划【五步总纲】
五步：
1.dp数组以及下标定义
dp[i]
2.递推公式
dp[n]=dp[n-1]+dp[n-2]
dp[n] = max(不包含dp[n-1])+nums[n]
dp[n] = min（dp[n-coin[i]]+1，dp[n]） 【注意+1前要判断dp[n-coin[i]]！=INT_MAX,防止+1溢出】
dp[n] = dp[i] && wordDict.find(s[i+1..j])!=wordDict.end()
3.dp数组如何初始化
注意：判断边界条件，n=0dp[1]就不存在【斐波那契】
dp[0]初始化为0【零钱兑换】
dp初始化为INT_MAX/0【此时一般会有dp[0] = 0,要不然无法迭代】
4.遍历顺序
for循环顺序
先遍历背包/物品？？？
5.打印数组【debug】
第一题：斐波那契数列
首先回顾了vector：
问题：1.emm for遍历是（初始化；满足条件；变量改变）
初始化，是否满足条件？，满足执行for{}里代码，然后执行变量改变
没有考虑n=0 ，dp[1]初始化是胡闹
class Solution {
public:
int fib(int n) {
std::vector<int> dp(n+1);//没有考虑n=0的时候不能初始化dp【1】
if(n==0){
return 0;
}
dp[0] = 0;
dp[1] = 1;
if(n == 0||n==1){
return dp[n];
}
for(int i = 2;i<=n;i++){//for先i<=n；然后i++
dp[i] = dp[i-1]+dp[i-2];
}
return dp[n];
}
};第二题：爬楼梯
感觉难点主要是 爬楼梯——>有几种方法
解决方案：少量列举：
n ==1,n==2,n==2
错误原因：emmm
for变量是i，{}里面循环的是n
class Solution {
public:
int climbStairs(int n) {
//方法数？
if(n==1){
return 1;
}
std:vector<int> dp(n+1);
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
};第三题：杨辉三角
刚开始在怀疑怎么输出
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]，但是函数返回vector<vector
缺陷：运行时报错， 初始化数组numRows，所以i应该是<numRows
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> dp(numRows);
for(int i = 0;i<numRows;i++){//i<
dp[i].resize(i + 1);
dp[i][0] = 1;
dp[i][i] = 1;
for (int j = 1; j < i; j++) {
dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
}
}
return dp;
}
};