70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
class Solution {
public:/* 方法一： 递归， 时间复杂度O（2^n）
int climbStairs(int n) {
if(n==1)
{
return 1;
}
else if(n==2)
{
return 2;
}
else if(n==3)
{
return 3;
}
else{
return climbStairs(n-1)+climbStairs(n-2);
}
}*/
//方法二： 使用一个数组和for 循环，时间复杂度O（n）
int climbStairs(int n)
{
if(n<=3)
{
return n;
}
int attr[n];
attr[0] = 1; //一节楼梯只有一种方法
attr[1] = 2; //两节楼梯有两种方法
attr[2] = 3;// 同理
for(int i=3;i<n;i++)
{
attr[i] = attr[i-1] + attr[i-2];
}
return attr[n-1];
}
};
746. 使用最小花费爬楼梯
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
示例 1：
输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
示例 2：
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
大致思路如下，
注意题目描述：每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯
所以示例1中只花费一个15 就可以到阶梯顶，最后一步可以理解为 不用花费。
读完题大家应该知道指定需要动态规划的，贪心是不可能了。
1.确定dp数组以及下标的含义
使用动态规划，就要有一个数组来记录状态，本题只需要一个一维数组dp[i]就可以了。
dp[i]的定义：到达第i个台阶所花费的最少体力为dp[i]。（注意这里认为是第一步一定是要花费）
对于dp数组的定义，大家一定要清晰！
2.确定递推公式
可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。
那么究竟是选dp[i-1]还是dp[i-2]呢？
一定是选最小的，所以dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
注意这里为什么是加cost[i]，而不是cost[i-1],cost[i-2]之类的，因为题目中说了：每当你爬上一个阶梯你都要花费对应的体力值
3.dp数组如何初始化
根据dp数组的定义，dp数组初始化其实是比较难的，因为不可能初始化为第i台阶所花费的最少体力。
那么看一下递归公式，dp[i]由dp[i-1]，dp[i-2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就够了，其他的最终都是dp[0]dp[1]推出。
所以初始化代码为：
vector dp(cost.size());
dp[0] = cost[0];
dp[1] = cost[1];
4.确定遍历顺序
最后一步，递归公式有了，初始化有了，如何遍历呢？
本题的遍历顺序其实比较简单，简单到很多同学都忽略了思考这一步直接就把代码写出来了。
因为是模拟台阶，而且dp[i]又dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了。
举例推导dp数组
示例：
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下：
代码如下：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
// dp 数组表示爬到每一节楼梯所耗费的体力值最小值
int dp[cost.size()];
dp[0] = cost[0];
dp[1] = cost[1];
for(int i=2;i<cost.size();i++)
{
dp[i] = min(dp[i-1],dp[i-2]) + cost[i];
}
return min(dp[cost.size()-1],dp[cost.size()-2]);
}
};