70. 爬楼梯(简单)

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

示例 1：

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

  1. 1 阶 + 1 阶

  2. 2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs

思路：

这里用回溯其实是可以的，但是很明显可以看到动态规划的影子，每一阶的台阶的走法，都等于前面一个台阶的走法和再往前面一个的走法，f(n)=f(n-1)+f(n-2),也就是变相的斐波那契数列，不对，其实就是fib问题

回看记录200518

递归用公式，要判断0和1，直接求得话就是dp，f3=f1+f2，f1=f2，f2=f3，要从i=2开始

回看记录200622

也是要考虑大数，和leetcode中不是很一致

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
  //f(n)=f(n-1)+f(n-2)
//本质就是斐波那契数列
class Solution {
    public int climbStairs(int n) {
        if(n<=2)
            return n;
        int f1 = 1,f2 = 2;
        int f3=0;
        for(int i=2;i<n;i++){
            f3 = f2+f1;
            f1=f2;
            f2=f3;
        } 
        return f3;
    }
}

class Solution {
    public int numWays(int n) {
        int a = 1, b = 1, sum;
        for(int i = 0; i < n; i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}

//另一种解决方法就是递归
int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}
//还有dp