天台网站建设,剪辑素材网站免费,北京免费自助建站模板,asp.net企业网站模板创作不易#xff0c;本篇文章如果帮助到了你#xff0c;还请点赞 关注支持一下♡#x16966;)!! 主页专栏有更多知识#xff0c;如有疑问欢迎大家指正讨论#xff0c;共同进步#xff01; 更多算法知识专栏#xff1a;算法分析#x1f525; 给大家跳段街舞感谢… 创作不易本篇文章如果帮助到了你还请点赞 关注支持一下♡)!! 主页专栏有更多知识如有疑问欢迎大家指正讨论共同进步 更多算法知识专栏算法分析 给大家跳段街舞感谢支持ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ LeetCode题解专栏【LeetCode刷题笔记】 目录 题目链接一、题目描述二、示例三、题目分析dp数组的定义基础情况递推公式 四、代码实现C优化 题目链接
70. 爬楼梯- 力扣LeetCode
一、题目描述
假设你正在爬楼梯。需要n阶你才能到达楼顶。
每次你可以爬1或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
二、示例
示例 1 输入n 2 输出2 解释有两种方法可以爬到楼顶。 1 阶 1 阶2 阶 示例 2 输入n 3 输出3 解释有三种方法可以爬到楼顶。 1 阶 1 阶 1 阶1 阶 2 阶2 阶 1 阶 三、题目分析
根据题目一次1个或2个台阶先考虑极端情况只有一个台阶的情况和只有两个台阶的情况 只有一个台阶1种方法爬1个台阶 只有两个台阶2种方法爬两次1个台阶、爬一次2个台阶
在两个台阶的问题中第一种方法包含了只有一个台阶的情况爬两次1个台阶即爬了一个台阶此时只剩下一个台阶转化为了只有一个台阶的问题
三个台阶时如果爬1个台阶还剩2个台阶转化为了2个台阶的问题如果爬两个台阶还剩1个台阶转化为了1个台阶的问题
因此三个台阶的方法等于一个台阶的方法 两个台阶的方法为动态规划问题
dp数组的定义
dp[i] 爬到第i层楼梯有dp[i]种⽅法
基础情况
第1个台阶和第2个台阶为最基础的情况分别是1种、2种方法
dp[1] 1; dp[2] 2;
递推公式
由题目分析可得dp[i] dp[i-1] dp[i-2]
四、代码实现C
class Solution {
public:int climbStairs(int n) {vectorint dp(n1);if(n 1) return n;if(n 2) return n;dp[1] 1;dp[2] 2;for(int i 3;i n; i){dp[i] dp[i-1] dp[i-2];}return dp[n];}
};优化
以三个台阶为例第三个台阶只依赖于前两个台阶的方法和第i个台阶只依赖于i - 1 和i - 2的和
只需关注前两个的值其余的可以不去考虑 vectorint dp(n1) 缩小为 dp[3]优化空间复杂度在数据n较大的情况下
class Solution {
public:int climbStairs(int n) {int dp[3]; //dp[0]占1个if(n 1) return n;if(n 2) return n;dp[1] 1;dp[2] 2;int sum 0;for(int i 3;i n; i){sum dp[1] dp[2];dp[1] dp[2];dp[2] sum;}return dp[2];}
};** ** 大家的点赞、收藏、关注将是我更新的最大动力 欢迎留言或私信建议或问题。
大家的支持和反馈对我来说意义重大我会继续不断努力提供有价值的内容
如果本文哪里有错误的地方还请大家多多指出(●◡●)
