LeetCode 70. 爬楼梯(动态规划)
发布日期:2021-07-01 03:40:22
浏览次数:2
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月17日 21时46分11秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
33 Qt 之绘图之绘制卡通蚂蚁
2019-05-02
34 Qt 之绘图之绘制时钟
2019-05-02
35 Qt 之绘制闪烁文本
2019-05-02
QT知识点总结(一)
2019-05-02
QT知识点总结(二)
2019-05-02
QT知识点总结(三)
2019-05-02
一劳永逸的解除ByondCompare4注册问题
2019-05-02
Unix环境变量--文件操作
2019-05-02
Unix环境变量--进程管理
2019-05-02
Unix环境变量--信号(一)
2019-05-02
Unix环境变量--线程基础
2019-05-02
Unix环境变量--缓冲区
2019-05-02
Unix环境变量--堆和栈的区别
2019-05-02
Unix环境变量--POSIX异步I/O
2019-05-02
UNIX环境变量--读写函数变体
2019-05-02
UNIX环境变量--存储映射I/O
2019-05-02
UNIX环境变量--IPC之管道通信
2019-05-02
C++虚继承【详解】
2019-05-02
tinyhttpd源码学习1
2019-05-02
Plus One
2019-05-02