假設(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 階

步驟一、確定狀態(tài):

確定dp數(shù)組以及下標(biāo)的含義
dp[i]: 爬到第i層樓梯，有dp[i]種方法

步驟二、推斷狀態(tài)方程:

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

第i階臺階，要么從第i?1階臺階邁一步， 要么從第i?2階臺階邁兩步，所以到第 i 階臺階的方法總數(shù)，就是到第i?1臺階的方法總數(shù)與到第i?2臺階方法總數(shù)之和

步驟三、規(guī)定初始條件:

初始條件:
dp[1] = 1, dp[2] = 2

步驟四、計(jì)算順序:

從前往后

先計(jì)算第1階:dp[1]

計(jì)算第2階:dp[2]
...

計(jì)算第最后一階:dp[n]

class Solution:def climbStairs(self, n: int) -> int:if n < 3: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]

總結(jié)

以上是生活随笔為你收集整理的84. Leetcode 70. 爬楼梯 (动态规划-基础题)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。