題目
假設(shè)你正在爬樓梯凳厢。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢审残？
注意：給定 n 是一個(gè)正整數(shù)。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂斑举。
- 1 階 + 1 階
- 2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂维苔。
- 1 階 + 1 階 + 1 階
- 1 階 + 2 階
- 2 階 + 1 階
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/climbing-stairs
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)懂昂，非商業(yè)轉(zhuǎn)載請注明出處介时。
狀態(tài)轉(zhuǎn)移方程
dp[i] = dp[i-1] + dp[i-2]
dp[i]表示爬到第i層有多少種爬法
爬到第i層有兩種爬法，從第i-1層爬上來和從第i-2層爬上來。
根據(jù)定義沸柔，第i層的爬法=第i-1層的爬法+第i-2層的爬法
Base
由狀態(tài)轉(zhuǎn)移方程可知
需要dp由i-1 和 i-2得出循衰，有意義的 & 最小的狀態(tài)轉(zhuǎn)移方程為i=3時(shí)。
dp[3] = dp[2] + dp[1]
答案
class Solution {
public int climbStairs(int n) {
// 邊界判斷
if (n < 3) {
return n;
}
// 這里注意dp的定義是：dp[i]表示爬到第i層有多少種爬法褐澎。
// 求第n層為dp[n]会钝，所以數(shù)組長度為n+1。
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
// i=1 & 2已知工三，直接從三開始
for (int i = 3; i < dp.length; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
