題目鏈接 => 戳這里

題目截圖

解析

動(dòng)態(tài)規(guī)劃四步走：
1.問(wèn)題拆解：

我們到達(dá)第n個(gè)樓梯可以從第n-1個(gè)或者第n-2個(gè)樓梯到達(dá)，因此對(duì)第N個(gè)問(wèn)題的求解就變成了對(duì)第n-1個(gè)問(wèn)題和第n-2個(gè)問(wèn)題的求解；

2.狀態(tài)定義：

從起點(diǎn)到達(dá)第n個(gè)樓梯的方法總數(shù)=從起點(diǎn)到達(dá)第n-1個(gè)樓梯的方法總數(shù)+從起點(diǎn)到達(dá)第n-2個(gè)樓梯的方法總數(shù)；

3.遞推方程

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

4.實(shí)現(xiàn)

在實(shí)現(xiàn)過(guò)程，除了關(guān)鍵性的遞推方程推導(dǎo)，還需要注意狀態(tài)的初始化；在這道題里面，我們需要獨(dú)立定義當(dāng)n=0,1,2時(shí)的狀態(tài)值；

題解

class Solution {
    public int climbStairs(int n) {
        // 無(wú)需推導(dǎo)狀態(tài)值可直接返回
        if (n < 3) {
            return n;
        }
        // 這是dp的基本操作，定義一個(gè)數(shù)組存儲(chǔ)中間狀態(tài)值
        int[] dp = new int[n+1];
        // 定義基本狀態(tài)值
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}