Leetcode70:爬楼梯(简单) 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
示例 1:
输入:n = 2【Leetcode|Leetcode70-爬楼梯(C语言)】示例 2:
输出:2
解释:有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
输入:n = 3提示:
输出:3
解释:有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
1 <= n <= 45
递归 超出时间限制
#include
#include
int climbStairs(int n){
if(n<0) return 0;
if(n==1) return 1;
if(n==2) return 2;
return climbStairs(n-1)+climbStairs(n-2);
}
int main(int argc, char *argv[]) {
int n;
scanf("%d",&n);
printf("%d",climbStairs(n));
return 0;
}
记忆化递归(找一个一维数组将重复计算的结果存储起来)
#include
#include
int m[50];
int climbStairs(int n){
int res;
if(n<0) return 0;
if(m[n]!=0) return m[n];
else
{
res = climbStairs(n-1)+climbStairs(n-2);
returnres;
}
}
int main(int argc, char *argv[]) {
int n,i;
for(i=0;
i<50;
i++) m[i]=0;
m[1]=1;
m[2]=2;
scanf("%d",&n);
printf("%d",climbStairs(n));
return 0;
}
动态规划
int climbStairs(int n){
int prepre=1,pre=2,i=0;
int res;
if(n==1) return 1;
if(n==2) return 2;
for(i=3;
i<=n;
i++)
{
res = prepre+pre;
prepre=pre;
pre=res;
}
return res;
}
三阶扩展 如果是一次只能上1阶或3阶楼梯。
#include
#include
int m[50];
int climbStairs(int n){
int res;
if(n<0) return 0;
if(m[n]!=0) return m[n];
else
{
res = climbStairs(n-1)+climbStairs(n-3);
returnres;
}
}
int main(int argc, char *argv[]) {
int n,i;
for(i=0;
i<50;
i++) m[i]=0;
m[1]=1;
m[2]=1;
m[3]=2;
scanf("%d",&n);
printf("%d",climbStairs(n));
return 0;
}
#include
#include
int climbStairs(int n){
int res,i;
int prepre=1,pre=1,preafter=2;
if(n==1 || n==2) return 1;
if(n==3) return 2;
for(i=4;
i<=n;
i++)
{
res = prepre+preafter;
prepre=pre;
pre=preafter;
preafter=res;
}
return res;
}
int main(int argc, char *argv[]) {
int n,i;
scanf("%d",&n);
printf("%d\n",climbStairs(i));
return 0;
}
推荐阅读
- 数据结构|数据结构之并查集(含代码实现)
- LeetCode|LeetCode 2028. 找出缺失的观测数据题解
- 剑指offer进阶|剑指offer103(最少的硬币数目)
- 剑指offer进阶|剑指offer85(生成匹配的括号)
- 蓝桥杯|蓝桥杯——乳草的入侵
- #|算法Day6(广度优先搜索——最短路径问题)
- JavaSE|MySQL 数据库约束、聚合查询、多表查询
- 植物大战数据结构|植物大战 队列 —— 纯C
- 论文解读|Query-Efficient Hard-label Black-box Attack: An Optimization-based Approach论文解读