70. 爬楼梯(动态规划入门详解与动态规划原理)
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1:
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2:
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
代码
class Solution {
public:
int climbStairs(int n) {
vector<int> dp(n+3,0);
dp[1]=1;
dp[2]=2;
for(int i = 3;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
};
为什么把vector的元素个数设置为n+3
呢? 明明用n个元素就可以了,n+3
个元素多占用了3个空间。
当n 等于0,1,2时,不用特殊处理,也就是说,不用if
语句判断。
这里要记得,i
就变成了从3开始,跳过dp[0]
,dp[1]
,dp[2]
这三个位置。
下面是dp[n+1]的写法
public int climbStairs(int n) {
if(n <=1)
return 1;
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];
}
动态规划原理
不熟悉vector 的同学可以看看 C++ vector 容器浅析。
CSDN-Ada助手: 哇, 你的文章质量真不错,值得学习!不过这么高质量的文章, 还值得进一步提升, 以下的改进点你可以参考下: (1)增加除了各种控件外,文章正文的字数;(2)提升标题与正文的相关性。
CSDN-Ada助手: 恭喜你这篇博客进入【CSDN每天值得看】榜单,全部的排名请看 https://bbs.csdn.net/topics/619321471。
CSDN-Ada助手: 恭喜你这篇博客进入【CSDN每天值得看】榜单,全部的排名请看 https://bbs.csdn.net/topics/619316331。
CSDN-Ada助手: 恭喜你这篇博客进入【CSDN每天值得看】榜单,全部的排名请看 https://bbs.csdn.net/topics/619307073。
weixin_42825047: 直接搜索 Go+Vue通用后台管理项目实战 就有了。