爬楼梯问题python
时间: 2023-07-28 07:51:34 浏览: 60
爬楼梯问题是一个经典的动态规划问题,可以用Python来求解。假设你要爬n级楼梯,每次可以爬1级或2级,那么有多少种不同的方法可以爬到楼顶呢?
我们可以使用递归或动态规划来解决这个问题。下面是使用动态规划的方法:
```python
def climbStairs(n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
dp = [0] * (n+1)
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
```
这个函数的参数是一个整数n,返回值是到达第n级楼梯的不同方法数。首先判断n是否等于1或2,如果是则直接返回1或2。创建一个长度为n+1的数组dp,dp[i]表示到达第i级楼梯的不同方法数。初始化dp[1]=1和dp[2]=2。然后从3开始遍历到n,每次计算dp[i]=dp[i-1]+dp[i-2]。最后返回dp[n]即可。
例如,如果n=3,那么dp数组的值为[0, 1, 2, 3],最终结果为3。如果n=4,那么dp数组的值为[0, 1, 2, 3, 5],最终结果为5。
相关问题
冬冬爬楼梯 python
冬冬爬楼梯的Python程序是一个经典的动态规划问题。根据引用,如果楼梯的阶数为5,则冬冬爬楼梯的方法有13种。根据引用,我们可以使用递归的方法来解决这个问题,即将楼梯的阶数减去1、2或3,直到减到0,然后返回结果的总和。
下面是一个冬冬爬楼梯的Python程序示例:
```python
def climb_stairs(n):
if n <= 0:
return 0
if n == 1:
return 1
if n == 2:
return 2
if n == 3:
return 4
return climb_stairs(n-1) + climb_stairs(n-2) + climb_stairs(n-3)
n = 5
ways = climb_stairs(n)
print("冬冬爬楼梯的方法有", ways, "种")
```
迭代法爬楼梯python
迭代法爬楼梯的Python实现如下所示:
```python
class Solution:
def climbStairs(self, n: int) -> int:
dp = [0 for _ in range(n+1)]
dp = 1
dp = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
```
这段代码使用动态规划的思想来解决爬楼梯的问题。dp[i]表示爬到第i级台阶的方法数。初始时,dp和dp都为1,表示爬到第0级和第1级台阶只有一种方法。
通过迭代计算,dp[i]可以由dp[i-1]和dp[i-2]得到,因为每一步只能走一个台阶或者两个台阶。最终返回dp[n]即可得到爬到第n级台阶的方法数。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *3* [python 爬楼梯 动态规划 算法 leetcode](https://blog.csdn.net/qq_50974223/article/details/112889642)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *2* [Leetcode 爬楼梯 (Python解法)](https://blog.csdn.net/weixin_42095500/article/details/82951947)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]