用Java代码实现:动态规划法解题:有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。
时间: 2024-05-03 20:20:34 浏览: 74
问题描述:有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。
5星 · 资源好评率100%
好的,以下是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]逐个计算出最终结果。
阅读全文