LeetCode-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

方法一：自上而下遞歸
class Solution{
public:
    vector<int> dp;
    int climbStairs(int n){
    	if(dp.empty()) dp.resize(n+1);
        if(n==1||n==2) return n;
        if(0 != dp[n]) return dp[n];
        int tmp = climbStairs(n-1)+climbStairs(n-2);
        dp[n] = tmp;
        return dp[n];
    }
};
或者：
class Solution {
public:
vector<int> dp;
    int climbStairs(int n) {
        if(dp.empty()) dp.resize(n+1);
        if(1==n ||2==n) return n;
        if(0==dp[n]) dp[n] = climbStairs(n-1)+climbStairs(n-2);
        return dp[n];
    }
};


方法二：自下而上疊代
class Solution {
public:
    int climbStairs(int n) {
    	if(n == 1) return 1;
    	int first = 1;
    	int second = 2;
    	for(int i = 3;i<=n;i++){
    		int third = first + second;
    		first = second;
    		second = third;
    	}
    	return second;
    }
};