題目鏈接 => 戳這里
題目截圖
解析
動態(tài)規(guī)劃四步走：
1.問題拆解：
我們到達(dá)第n個(gè)樓梯可以從第n-1個(gè)或者第n-2個(gè)樓梯到達(dá)吞加，因此對第N個(gè)問題的求解就變成了對第n-1個(gè)問題和第n-2個(gè)問題的求解囤采；
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ān)鍵性的遞推方程推導(dǎo)祥楣，還需要注意狀態(tài)的初始化类垫；在這道題里面寿桨，我們需要獨(dú)立定義當(dāng)n=0,1,2時(shí)的狀態(tài)值此衅；
題解
class Solution {
public int climbStairs(int n) {
// 無需推導(dǎo)狀態(tài)值可直接返回
if (n < 3) {
return n;
}
// 這是dp的基本操作，定義一個(gè)數(shù)組存儲中間狀態(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];
}
}
