70. Climbing Stairs

1.問題

• 一次只可以向前1或格, 有多少種方法到達終點?

2.想法

• 提問:

• function header, parameter

• test input

• 說明想法

  • 動態規劃: 由步伐的種類有一步跟兩步, 可以知道到目前所在的位置可以由前一個位置或是前前一個位置而來, 因此到目前位置的所有可能方式為到前個位置的可能 + 到前前個位置的可能

• 測試計算複雜度

3.程式碼

class Solution {
public:
    int climbStairs(int n) {
        if ( n == 0) {
            return 0;
        }
        vector<int> cache(n, -1);
        return climb(n - 1, cache);
    }
private:
    int climb(int i, vector<int>& cache) {
        if (i == 0) {
            return 1;
        } else if (i == 1) {
            return 2;
        } 
        
        if (cache[i] == -1){
            cache[i] = climb(i - 1, cache) + climb(i - 2, cache);  
        }
        return cache[i];
    }
};