【Climbing Stairs】cpp
2024-09-05 04:40:45
题目:
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
代码:
class Solution {
public:
int climbStairs(int n) {
int prev = ;
int curr = ;
for (int i = ; i<n; ++i)
{
const int tmp = curr;
curr = curr + prev;
prev = tmp;
}
return curr;
}
};
Tips:
1. 这道题可以抽象成求Fibonacci数列的通项(只看最后一步:从n-1到n迈一个台阶;从n-2到n迈两个台阶)
==================================================
第二次过这道题,没有想到直接用斐波那契数列的思想。
首先想到的做法是直接递归,结果超时;后来想到可以用一个记忆hashmap,保存计算过的中间结果,于是有了下面0msAC的代码。
class Solution {
public:
int climbStairs(int n)
{
map<int, int> calculated;
calculated[] = ;
calculated[] = ;
return Solution::subStairs(n, calculated);
}
static int subStairs(int n, map<int, int>& calculated)
{
if ( n== ) return ;
if ( n== ) return ;
int way1 = calculated.find(n-)!=calculated.end() ? calculated[n-] : calculated[n-]=Solution::subStairs(n-, calculated);
int way2 = calculated.find(n-)!=calculated.end() ? calculated[n-] : calculated[n-]=Solution::subStairs(n-, calculated);
return way1+way2;
}
};
tips:
这个思路还是非常通用的。
原来斐波那契数列思路的非递归实现也要记住,这段代码也很漂亮。
最新文章
- MySQL多实例安装
- 性能测试之--Apache JMeter安装
- linux查看某个进程的线程id(spid)
- js获取页面宽度高度及屏幕分辨率
- 正则表达式的使用(C++)
- 泡泡堂、QQ堂游戏通信架构分析
- vim常用命令 vim键盘布局
- 两个UIView添加同一个手势只有最后一个有用
- 路由器密码破解工具 Hydra 7.5
- C#实现树的双亲表示法
- Cordova CLI源码分析(一)——简介
- Oracle SQL Developer 免费的DB2客户端
- Noname
- linux驱动 之 module_init解析 (上)【转】
- UVA1401 Remember the Word
- Docker(十九)-Docker监控容器资源的占用情况
- 巧用CurrentThread.Name来统一标识日志记录
- sql 按字段指定值排序
- 重识linux-压缩文件的原理
- ice服务初探