使用python写假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。
时间: 2023-11-26 20:48:02 浏览: 28
以下是使用Python解决该问题的代码和解释:
```python
def climbStairs(n):
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]
```
解释:
这是一个动态规划问题。我们可以使用一个数组dp来存储到达每个台阶的不同方法数。dp[i]表示到达第i个台阶的不同方法数。显然,到达第一个台阶只有一种方法,到达第二个台阶有两种方法。对于第i个台阶,我们可以从第i-1个台阶爬1步到达,也可以从第i-2个台阶爬2步到达。因此,dp[i] = dp[i-1] + dp[i-2]。最后返回dp[n]即可。
相关问题
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
这是一个经典的动态规划问题。我们可以用一个数组 dp 来记录到达每个台阶的不同方法数,其中 dp[i] 表示到达第 i 个台阶的不同方法数。根据题意,可以得出以下状态转移方程:
dp[i] = dp[i-1] + dp[i-2]
意思是到达第 i 个台阶的不同方法数等于到达第 i-1 个台阶的不同方法数加上到达第 i-2 个台阶的不同方法数。因为每次可以爬 1 或 2 个台阶,所以到达第 i 个台阶的方法数只能是从第 i-1 或 i-2 个台阶转移而来。
初始状态为 dp[0] = 1,表示到达第 0 个台阶的方法数为 1(也就是不用爬);dp[1] = 1,表示到达第 1 个台阶的方法数为 1(只能爬 1 个台阶)。
最终的答案为 dp[n],表示到达第 n 个台阶的不同方法数。
下面是具体的 Python 代码实现:
```python
def climbStairs(n: int) -> int:
if n <= 1:
return 1
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
```
时间复杂度为 O(n),空间复杂度为 O(n)。
使用python3.0x编写程序, 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
以下是使用Python3编写的解决方案:
```python
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
elif n == 2:
return 2
else:
a, b = 1, 2
for i in range(3, n+1):
a, b = b, a+b
return b
```