算法题:假如一次可以上1或2台阶,有n个台阶,n的取值范围:1到45,有多少种方式,到n个台阶?Java实现
时间: 2024-02-28 15:56:27 浏览: 15
同样是斐波那契数列问题,可以使用动态规划算法来解决。Java代码如下:
```java
public int climbStairs(int n) {
if(n == 1) return 1;
if(n == 2) return 2;
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
for(int i=3; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
```
时间复杂度为O(n),可以在瞬间得到结果。需要注意的是,当n较大时,需要使用long类型的变量来保存dp数组的值,避免溢出。
相关问题
算法题:假如一次可以上1或2台阶,有n个台阶,n的取值范围:1到45,有多少种方式,到n个台阶?
这是一个经典的斐波那契数列问题。假设到达第n个台阶的方法数为f(n),那么有以下递推式:
f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2)
这个递推式的意思是,到达第n个台阶的方法数等于到达第n-1个台阶的方法数加上到达第n-2个台阶的方法数。因为每次可以走1个或2个台阶,所以到达第n个台阶的方法数只能从第n-1个台阶或第n-2个台阶转移而来。
根据递推式可以用动态规划算法来解决这个问题,时间复杂度为O(n)。具体地,可以用一个数组dp来保存每个台阶的方法数,初始化dp[1]=1, dp[2]=2,然后从3到n依次计算dp[i]的值,最终返回dp[n]即可。
下面是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=45时,该算法的运行时间约为0.1ms,可以在瞬间得到结果:
```
>>> climbStairs(45)
1836311903
```
假设有2种上楼梯的步伐:1个台阶/步,2个台阶/步。从1楼到2楼有n级台阶。有多少种不同的走法。
这是一个经典的斐波那契数列问题,可以使用递归或动态规划来解决。
首先考虑递归方法。设 `f(n)` 表示走到第 `n` 级台阶的不同走法数量,则有以下递推式:
```
f(n) = f(n-1) + f(n-2)
```
解释一下,走到第 `n` 级台阶可以从第 `n-1` 级台阶走一步或者从第 `n-2` 级台阶走两步到达。当 `n=1` 时,只有一种走法;当 `n=2` 时,有两种走法(一步一步走或者直接跨两步)。
根据递推式,可以编写如下的递归函数来求解:
```python
def count_ways(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return count_ways(n-1) + count_ways(n-2)
```
然而,这种递归方法会有很多重复计算,导致时间复杂度非常高,随着 `n` 的增加,计算时间会指数级增长。
因此,我们可以使用动态规划(DP)来优化算法。具体来说,我们可以使用一个数组 `dp` 来记录到每个台阶的不同走法数量,初始值为 `dp[1] = 1, dp[2] = 2`,然后使用递推式 `dp[i] = dp[i-1] + dp[i-2]` 来计算剩余的值。最后,返回 `dp[n]` 即可。
下面是使用动态规划的代码实现:
```python
def count_ways(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
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` 级台阶的不同走法数量了。