代码随想录34 动态规划
1.经典问题：
背包问题
打家劫舍
斐波那契数列
爬楼梯问题
股票问题
2.dp数组以及下标的含义
3.递推公式
3.dp数组初始化
4.遍历顺序
5.打印数组
leetcode509.斐波那契数列
1.确定dp[i]含义 dp[i]第i个斐波那契数的值为dp[i]
2.递推公式：dp[i]=dp[i-1]+dp[i+2]
3.dp数组如何初始化 dp[0]=1 dp[1]=1（很多时候，初始化是依赖递推公式的）
4.遍历顺序
5.打印数组
如果小于等于1，一定要直接输出，挡在后面初始化前面，要不然会报错
class Solution {
public:
int fib(int N) {
if (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];
}
};
leetcode70.爬楼梯
楼梯的每一层都是基于前面一层或是前前一层的,就是换皮的斐波那契数列
class Solution {
public:
int climbStairs(int n) {
vector<int>louti(n+1);//括号里是要初始化多少个数组元素
if(n==1){
return 1;
}
else if(n==2){
return 2;
}
louti[1]=1;
louti[2]=2;
for(int i=3;i<=n;i++){
louti[i]=louti[i-1]+louti[i-2];
}
return louti[n];
}
};