70.爬楼梯
题目详情
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
示例 1:
输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2:
输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
提示:
1 <= n <= 45
思路
我们用 f(x) 表示爬到第 x 级台阶的方案数,考虑最后一步可能跨了一级台阶,也可能跨了两级台阶,所以我们可以列出如下式子:
f(x)=f(x−1)+f(x−2)
它意味着爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。很好理解,因为每次只能爬 1 级或 2 级,所以 f(x) 只能从 f(x−1) 和 f(x−2) 转移过来,而这里要统计方案总数,我们就需要对这两项的贡献求和。
以上是动态规划的转移方程,下面我们来讨论边界条件。我们是从第 0 级开始爬的,所以从第 0 级爬到第 0 级我们可以看作只有一种方案,即 f(0)=1;从第 0 级到第 1 级也只有一种方案,即爬一级,f(1)=1。这两个作为边界条件就可以继续向后推导出第 n 级的正确结果。我们不妨写几项来验证一下,根据转移方程得到 f(2)=2,f(3)=3,f(4)=5,……
代码解答
class Solution {
public:
int climbStairs(int n) {
int f1 = 0;
int f2 = 0;
int result = 1;
for(int i = 1;i <= n;i++){
f1 = f2;
f2 = result;
result = f1 + f2;
}
return result;
}
};
746.使用最小花费爬楼梯
题目详情
给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。
一旦你支付此费用,即可选择向上爬 一个 或者 两个 台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的 最低 花费,即最后一步之后的那个位置(下标 cost.length)。
示例 1:
输入:cost = [10,15,20]
输出:15
解释:你将从下标为 1 的台阶开始。
- 支付 15 ,向上爬两个台阶,到达楼梯顶部。
总花费为 15 。
示例 2:
输入:cost = [1,100,1,1,1,100,1,1,100,1]
输出:6
解释:你将从下标为 0 的台阶开始。
- 支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。
- 支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。
- 支付 1 ,向上爬一个台阶,到达楼梯顶部。
总花费为 6 。
提示:
2 <= cost.length <= 10000 <= cost[i] <= 999
思路
假设数组 cost 的长度为 n,则 n 个阶梯分别对应下标 0 到 n−1,楼层顶部对应下标 n,问题等价于计算达到下标 n 的最小花费。可以通过动态规划求解。
创建长度为 n+1 的数组 dp,其中 dp[i] 表示达到下标 i 的最小花费。
由于可以选择下标 0 或 1 作为初始阶梯,因此有 dp[0]=dp[1]=0。
当 2≤i≤n 时,可以从下标 i−1 使用 cost[i−1] 的花费达到下标 i,或者从下标 i−2 使用 cost[i−2] 的花费达到下标 i。为了使总花费最小,dp[i] 应取上述两项的最小值,因此状态转移方程如下:
dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2]) 依次计算 dp 中的每一项的值,最终得到的 dp[n] 即为达到楼层顶部的最小花费。
代码
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1);
dp[0] = dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
};
509.斐波那契数
题目描述
斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1
给定 n ,请计算 F(n) 。
示例 1:
输入:n = 2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2:
输入:n = 3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3:
输入:n = 4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3
提示:
0 <= n <= 30
思路
递归方法时间复杂度太大了,用动态规划
斐波那契数的边界条件是 F(0)=0 和 F(1)=1。当 n>1 时,每一项的和都等于前两项的和,因此有如下递推关系:
F(n)=F(n−1)+F(n−2)
代码
class Solution {
public:
int fib(int n) {
if(n==0){
return 0;
}
if(n==1){
return 1;
}
return fib(n-1) + fib(n-2);
}
};
class Solution {
public:
int fib(int n) {
if(n==0){
return 0;
}
if(n==1){
return 1;
}
int p = 0,q = 0,r = 1;
for(int i=2;i<=n;i++){
p = q;
q = r;
r = p + q;
}
return r;
}
};
- 第一段代码(递归法):时间复杂度为 O(2ⁿ),效率极低。
- 第二段代码(迭代法):时间复杂度为 O(n),效率很高。
动态规划就是用局部最优推出全局最优,也就是第二段迭代法,自底向上

