用Java代码实现:动态规划法解题:有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。
时间: 2024-05-03 18:20:34 浏览: 8
好的,以下是Java代码实现:
```
public static int climbStairs(int n) {
if (n == 1) return 1; // 只有一级台阶,只有一种方法
if (n == 2) return 2; // 两级台阶,两种方法:一步一步上,或者直接跨两步
int[] dp = new int[n]; // 初始化
dp[0] = 1;
dp[1] = 2;
for (int i = 2; i < n; i++) {
dp[i] = dp[i-1] + dp[i-2]; // 动态转移方程
}
return dp[n-1];
}
```
该函数接受一个参数n,表示台阶的数量,返回一个整数,表示走完n级台阶的方法数。该实现采用了动态规划的思想,用一个数组存储每个台阶的方法数,根据动态转移方程dp[i] = dp[i-1] + dp[i-2]逐个计算出最终结果。
相关问题
上台阶问题:有n级台阶,每步可以走一级或两级,问有多少种不同的走法python
可以使用递归或动态规划来解决这个问题。
方法一:递归
递归的思路是,如果当前在第n级台阶上,则可以走一步到达n-1级台阶,或者走两步到达n-2级台阶。因此,到达第n级台阶的不同走法数就是到达n-1级台阶和到达n-2级台阶的不同走法数之和。
代码如下:
```python
def climbStairs(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return climbStairs(n-1) + climbStairs(n-2)
```
方法二:动态规划
动态规划的思路是,用一个数组dp来记录到达每个台阶的不同走法数。初始状态是dp[1]=1和dp[2]=2,然后根据递推公式dp[i]=dp[i-1]+dp[i-2],依次计算出dp[3]、dp[4]、...、dp[n]。
代码如下:
```python
def climbStairs(n):
if n == 1:
return 1
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]
```
两种方法的时间复杂度都是O(n),但是递归方法的空间复杂度比较高,可能会导致栈溢出,因此建议使用动态规划方法。
小明爬楼梯,如果每次可以上一个台阶或者两个台阶或者3个台阶,那么上 n 级台阶一共有多少种方案?
这道题可以使用递归或者动态规划来解决。
首先考虑递归,对于上 n 级台阶,小明可以从 n-1 级、n-2 级或者 n-3 级上来,所以总方案数为到 n-1 级、n-2 级和 n-3 级的方案数之和。可以得到递推公式:
f(n) = f(n-1) + f(n-2) + f(n-3)
其中 f(1) = 1, f(2) = 2, f(3) = 4。
使用递归需要注意的是,当 n 很大时,会出现重复计算的问题,导致时间复杂度变高,所以需要使用记忆化搜索或者动态规划来优化。
下面给出使用动态规划的解法:
设 dp[i] 表示到达第 i 级台阶的方案数,则有:
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
边界条件为 dp[1] = 1, dp[2] = 2, dp[3] = 4。
最终答案为 dp[n]。
代码如下(使用 Python 实现):
```python
def climb_stairs(n):
if n == 1:
return 1
if n == 2:
return 2
if n == 3:
return 4
dp = [0] * (n+1)
dp[1], dp[2], dp[3] = 1, 2, 4
for i in range(4, n+1):
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
return dp[n]
```
当输入 n=4 时,输出为 7;当输入 n=5 时,输出为 13。