70. Climbing Stairs

動規五部曲分別為:

1. 確定dp數組(dp table)以及下標的含義

2. 確定遞推公式

3. dp數組如何初始化

4. 確定遍歷順序

5. 舉例推導dp數組

(from 代碼隨想錄)

1. 確定dp數組(dp table)以及下標的含義

dp[i] 代表爬 n 階樓梯有幾種排列

2. 確定遞推公式

dp[i] = dp[i-1] + dp[i-2]

3. dp數組如何初始化

dp[0] = 1, dp[1] = 1

4. 確定遍歷順序

由左到右

5. 舉例推導dp數組

[1, 1, 2, 3, 5, 8.....]

class Solution {

public:

    int climbStairs(int n) {

        vector<int> dp(n+1, 0);

        dp[0] = dp[1] = 1;

        for(int i=2; i<=n; i++)

            dp[i] = dp[i-1] + dp[i-2];

        return dp.back();

    }

};