计算小明爬楼梯数量递推法用Python
时间: 2023-12-25 16:26:11 浏览: 50
计算小明爬楼梯数量的递推法是一种常见的动态规划算法,可以用Python实现。具体实现方法如下:
```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表示楼梯的阶数,函数返回小明爬楼梯的方案数。这个算法的时间复杂度为O(n),空间复杂度为O(n)。
相关问题
python小明爬楼梯
假设小明要爬n阶楼梯,他每次可以爬1阶或2阶,问小明有多少种不同的爬楼梯方式。
这是一个典型的斐波那契数列问题,可以用递归或动态规划来解决。
1. 递归方法
递归式为:f(n) = f(n-1) + f(n-2),初始条件为f(1) = 1, f(2) = 2。
代码如下:
```python
def climbStairs(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return climbStairs(n-1) + climbStairs(n-2)
```
但是,递归方法会重复计算很多次,效率较低。
2. 动态规划方法
递推式为:f(n) = f(n-1) + f(n-2),初始条件为f(1) = 1, f(2) = 2。
代码如下:
```python
def climbStairs(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
a = 1
b = 2
for i in range(3, n+1):
c = a + b
a = b
b = c
return b
```
这种方法效率更高,因为它将中间结果存储起来,避免了重复计算。
python用递推法计算sin x
以下是Python递推法计算sin x的示例代码:
```python
import math
def sin(x):
x = math.radians(x) #将角度转换为弧度
result = 0
term = x
i = 1
while(abs(term) > 1e-10): #精度控制
result += term
term *= (-1) * x * x / ((2 * i) * (2 * i + 1))
i += 1
return result
print(sin(30)) #输出sin(30°)
```
运行结果为:
```
0.49999999999999994
```
注意:由于计算机的精度限制,最终结果可能略有误差。