leetcode-70. Climbing Stairs

原题描述：

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

1、边界条件：n > 0，且为整数，即正整数

2、思路：n = 1，只有一种走法 ret = 1；n = 2，每次走一步和一次走两步两种走法；n > 3，n = 2 和 n = 1的走法之和，即从前面n - 1级走1级和n - 2级走2级就可以到 n, 加和。

可以用递归recursion，也可以化为迭代itrator。

3、代码实现

1）递归

1     public int climbStairs(int n) {
2         if (n == 1) {
3             return 1;
4         } else if (n == 2) {
5             return 2;
6         }
7         return climbStairs(n - 1) + climbStairs(n - 2);
8     }

class Solution {
    int[] rec;
    public int climbStairs(int n) {
        rec = new int[n];
        int i = 0;
        while (i < n) {
            rec[i++] = 0;
        }
        return climbStairsEx(n);
    }

    public int climbStairsEx(int n) {
        if (n == 1) {
         return 1;
        } else if (n == 2) {
         return 2;
        }
        if (rec[n - 1] != 0) {
            return rec[n - 1];//已经计算，不需要再次计算
        }
        rec[n - 1] = climbStairsEx(n - 1) + climbStairsEx(n - 2);
        return rec[n - 1];
    }
}

2）迭代

 1     public int climbStairs(int n) {
 2         int numPre1 = 0;
 3         int numPre2 = 0;
 4         int num = 0;
 5         for (int i = 1; i <= n; i++) {
 6             if (i == 1) {
 7                 num = 1;
 8             } else if (i == 2) {
 9                 num = 2;
10             } else {
11                 num = numPre1 + numPre2;
12             }
13             numPre2 = numPre1;
14             numPre1 = num;
15         }
16         return num;
17     }

1     public int climbStairs(int n) {
2         int a = 1, b = 1;
3         while (n-- > 0) {
4             b += a;
5             a = b - a;
6         }
7         return a;
8     }

4、时间复杂度：迭代O(n)，第一种递归递归会重复计算很多值，时间复杂度非常高，优化后把计算过的值存贮下来DP，避免重复计算O(n)；

空间复杂度：递归O(n)，但是递归会用到系统栈资源，迭代O(1)

5、api

无