算法：70. 爬楼梯

70. 爬楼梯
假设你正在爬楼梯。须要 n 阶你才气到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

1. <strong>输入：</strong>n = 2
2. <strong>输出：</strong>2
3. <strong>解释：</strong>有两种方法可以爬到楼顶。
4. 1. 1 阶 + 1 阶
5. 2. 2 阶

复制代码

示例 2：

1. <strong>输入：</strong>n = 3
2. <strong>输出：</strong>3
3. <strong>解释：</strong>有三种方法可以爬到楼顶。
4. 1. 1 阶 + 1 阶 + 1 阶
5. 2. 1 阶 + 2 阶
6. 3. 2 阶 + 1 阶

复制代码

提示：

• 1 <= n <= 45
  

解法1: 

1. class Solution {
2.     public int climbStairs(int n) {
3.         int p = 0, q = 0, r = 1;
4.         for (int i = 1; i <= n; ++i) {
5.             p = q;
6.             q = r;
7.             r = p + q;
8.         }
9.         return r;
10.     }
11. }
12.                 //i p q r
13.                 //1 0 0 1
14.                 //2 0 1 1
15.                 //3 1 1 2
16.                 //4 1 2 3
17.                 //5 2 3 5
18.                 //6 3 5 8
19.                 //7 5 8 13

复制代码

解法2： 

1. class Solution {
2.     public int climbStairs(int n) {
3.         int[] dp = new int[n + 1];
4.         dp[0] = 1;
5.         dp[1] = 1;
6.         for(int i = 2; i <= n; i++) {
7.             dp[i] = dp[i-1] + dp[i-2];
8.         }
9.         return dp[n];
10.     }
11. }
12.                 //i i-2 i-1 dp[i]
13.                 //0 0 0 1
14.                 //1 0 1 1
15.                 //2 1 1 2
16.                 //3 1 2 3
17.                 //4 2 3 5
18.                 //5 3 5 8
19.                 //6 5 8 13

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。