题目1：509 斐波那契数
题目链接：509 斐波那契数
题意
斐波那契数列由0和1开始 后面的每一项数字都是前面两项数字之和 计算F(n)
动态规划
动规五部曲：
1）dp数组及下标i的含义
dp[i] : 第i个斐波那契数值 i: 第i个斐波那契数
2）递推公式
dp[i] = dp[i-1] + dp[i-2]
3）dp数组初始化
dp[0] = 0 dp[1] = 1
4）遍历顺序
dp[i]由dp[i-1]和dp[i-2]得到，所以从前向后遍历
5）打印dp数组
代码
class Solution {
public:
int fib(int n) {
if(n<=1) return n;
vector<int> dp(n+1);
//dp数组初始化
dp[0] = 0;
dp[1] = 1;
for(int i=2;i<=n;i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};- 时间复杂度：O(n)
- 空间复杂度：O(n)
题目2：70 爬楼梯
题目链接：70 爬楼梯
题意
爬楼梯需要n阶才能到达楼顶（n>=0），每次可以爬1或2个台阶，爬到楼顶有几种方法
动态规划
动规五部曲：
1）dp数组及下标i的含义
dp[i] : 达到第i阶楼梯有dp[i]种方法 i: 第i阶楼梯
2）递推公式
dp[i] = dp[i-1] + dp[i-2]
3）dp数组初始化
n>=0 dp[0]没有意义 dp[1] = 1 dp[2] = 2
4）遍历顺序
dp[i]由dp[i-1]和dp[i-2]得到，所以从前向后遍历
5）打印dp数组
代码
class Solution {
public:
int climbStairs(int n) {
if(n<=2) return n;
vector<int> dp(n+1);
//dp数组初始化
dp[1] = 1;
dp[2] = 2;
for(int i=3;i<=n;i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};- 时间复杂度：O(n)
- 空间复杂度：O(n)
题目3：746 使用最小花费爬楼梯
题目链接：746 使用最小花费爬楼梯
题意
整数数组的元素cost[i]是从楼梯第i个台阶向上爬需要支付的费用 该费用可支持向上爬1个或两个台阶，可以选择下标为0或1的台阶开始爬 返回到达楼顶的最低费用
动态规划
动规五部曲：
1）dp数组及下标i的含义
dp[i] : 达到第i阶楼梯最少需要花费dp[i] i: 第i阶楼梯
2）递推公式
dp[i] = min ( dp[i-1] + const[i-1]， dp[i-2] + const[i-2] )
3）dp数组初始化
因为可以选择下标0或1的台阶往上爬 dp[0] = 0 dp[1] = 0
4）遍历顺序
dp[i]由dp[i-1]和dp[i-2]得到，所以从前向后遍历
5）打印dp数组
代码
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size()+1);
//初始化
dp[0] = 0;
dp[1] = 0;
for(int i=2;i<=cost.size();i++){
dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[cost.size()];
}
};- 时间复杂度：O(n)
- 空间复杂度：O(n)
