LeetCode 70. 爬楼梯(动态规划)
发布日期:2021-07-01 03:40:22
浏览次数:3
分类:技术文章
本文共 897 字,大约阅读时间需要 2 分钟。
题目链接:
之前在中讲过这个问题,现在用动态规划求解。
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。用dp[i] 表示到达第i个台阶的走法,那么到达第n个台阶的这个状态的走法,只跟n-1和n-2的状态有关(走1步或2步到n)
状态方程为 dp[n] = dp[n-1] + dp[n-2]class Solution { public: int climbStairs(int n) { if(n == 1) return 1; if(n == 2) return 2; int dp[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]; }};
对上面程序进行状态压缩,前面用不到的状态不保留
class Solution { public: int climbStairs(int n) { if(n == 1) return 1; if(n == 2) return 2; int dp_i, dp_i_2 = 1, dp_i_1 = 2; for(int i = 2; i < n; ++i) { dp_i = dp_i_1 + dp_i_2; dp_i_2 = dp_i_1; dp_i_1 = dp_i; } return dp_i; }};
转载地址:https://michael.blog.csdn.net/article/details/98478956 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月10日 14时05分12秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
QQ号终于能修改了?
2019-05-02
Kafka如果丢了消息,怎么处理的?
2019-05-02
1.3 万亿条数据查询,如何做到毫秒级响应?
2019-05-02
Spring Boot 项目瘦身指南,瘦到不可思议!
2019-05-02
高赞回答:为什么高级程序员不必担心自己的技术过时?
2019-05-02
支持 Dubbo 接口文档生成的工具
2019-05-02
开源!基于SpringBoot的车牌识别系统(附项目地址)
2019-05-02
Redis热点:如何发现Key问题?附5种解决方案
2019-05-02
SpringBoot集成WebSocket,实现后台向前端推送信息
2019-05-02
基于SpringBoot实现单点登录系统
2019-05-02
这位“华为天才少年”,竟然要我用“充电宝”打《只狼》
2019-05-02
优秀程序员早就学会用“状态模式”代替if-else了
2019-05-02
加强版Redis,又一款国产高性能KV存储数据库开源了!
2019-05-02
介绍一款基于 SpringBoot 开发 OA 开源产品 !
2019-05-02
Github 买 Star?
2019-05-02
小心了!通过一张照片我能找到你拍照的精确位置!
2019-05-02
使用基于 SpringMVC 的透明 RPC 开发微服务
2019-05-02
写“好”代码的十九条准则
2019-05-02
推荐几款 Redis 可视化工具
2019-05-02
送60本书!!
2019-05-02