题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
思考
- 1、这道题其实和斐波那契数列差不多
- 2、这题主要的难度就是判断出题型,和推导出递推公式
代码和注释
/**
动态规划
1、动态数组下标的意义
2、动态方程
3、初始条件
4、遍历顺序
5、log
*/
class Solution {
public int climbStairs(int n) {
// 边界
if(n <= 2){
return n;
}
// 下标是几种方法
int[] dp = new int[n +1];
// 递推公式 dp[i] = dp[i-1] + dp[i-2]
// 初始化
dp[1] = 1;
dp[2] = 2;
// 前到后遍历
for(int i = 3; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
总结
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/96119.html