代码随想录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];}
};