【玩轉(zhuǎn)動態(tài)規(guī)劃專題】70. 爬樓梯【簡單】

1、力扣鏈接

https://leetcode.cn/problems/climbing-stairs/description/

2、題目描述

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

示例 1：

輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂。

1. 1 階 + 1 階
2. 2 階
   示例 2：

輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂。

1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

提示：

1 <= n <= 45

3、題目分析

動態(tài)規(guī)劃五部曲：
1、確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[i]以及下標(biāo)的含義：i階樓梯有dp[i]種方式到達(dá)樓頂
2、確定遞推公式
dp[i] = dp[i-1]+dp[i-2];
3、dp數(shù)組如何初始化
注意讀題dp[0]是不存在的 題目中 1 <= n <= 45
所以初始化時從1開始，雖然設(shè)定dp[0] = 1也可以通過，但dp[0] = 1的意義不正確，與dp[i]數(shù)組的含義違背【0階樓梯有1種方式到達(dá)樓頂明顯不對】
正確初始化：
dp[1] = 1, dp[2]=2
4、確定遍歷順序
從前往后直接遍歷
5、舉例推導(dǎo)dp數(shù)組

4、代碼實現(xiàn)

1、Java

class Solution {public int climbStairs(int n) {//dp[i]以及下標(biāo)的含義：i階樓梯有dp[i]種方式到達(dá)樓頂int[] dp = new int[n+1];dp[1] = 1;dp[2] = 2;if(n < 3){return dp[n];}for(int i=3;i<=n;i++){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
}

2、C++

class Solution {
public:int climbStairs(int n) {if (n <= 1) return n; // 因為下面直接對dp[2]操作了，防止空指針vector<int> dp(n + 1);dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) { // 注意i是從3開始的dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};

3、python

class Solution:def climbStairs(self, n: int) -> int:if n <= 1:return ndp = [0] * (n + 1)dp[1] = 1dp[2] = 2for i in range(3, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n]

4、go

func climbStairs(n int) int {if n == 1 {return 1}dp := make([]int, n+1)dp[1] = 1dp[2] = 2for i := 3; i <= n; i++ {dp[i] = dp[i-1] + dp[i-2]}return dp[n]
}