您的位置:首页 > 健康 > 美食 > LeetCode70:爬楼梯

LeetCode70:爬楼梯

2024/11/14 13:08:46 来源:https://blog.csdn.net/Ricky_youngone/article/details/142290443  浏览:    关键词:LeetCode70:爬楼梯
class Solution {
public:int climbStairs(int n) {if(n == 1)  return 1;if(n == 2)  return 2;vector<int> dp(n + 1, 0);dp[1] = 1;dp[2] = 2;for(int i = 3; i < n +1; i++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};

这个题目也就是最简单的动态规划,题目很难理解,实际上当你递推几个之后就好办了很多。

n = 1 有1种方法

n = 2 有2种方法

n = 3 有3种方法

n = 4 有5种方法

n = 5 有8种方法

也就是斐波那契数列,区别就在n = 0时,这个题目没有n = 0,也就是没有0阶楼梯这一说法

看着程序员卡尔的动态规划五部曲也就是五步走,然后确定dp状态转移方程,最后算出来n的时候有多少种方法走上台阶。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com