盒子
盒子

70_爬楼梯_leetcode

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶
    输入: 3
    输出: 3
    解释: 有三种方法可以爬到楼顶。
  3. 1 阶 + 1 阶 + 1 阶
  4. 1 阶 + 2 阶
  5. 2 阶 + 1 阶

题解: 经典动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 动态规划
*/
class Solution {
public int climbStairs(int n) {
if (n == 1 || n == 2) {
return n;
}
int[] dp = new int[n];
dp[0] = 1; // 第一个阶梯有一种爬法
dp[1] = 2; // 第二个阶梯有两种爬法
for (int i = 2; i < n; i++) {
dp[i] = dp[i -1] + dp[i - 2];
}
return dp[n - 1];
}
}

AC传送门leetcode
欢迎关注公众号: 算法小生

支持一下
扫一扫,支持沈健
  • 微信扫一扫
  • 支付宝扫一扫