首页 > 代码库 > leetcode Climbing Stairs
leetcode Climbing Stairs
n个台阶，每次可以走一步或者两步，总共有多少种走法。
第一感觉想到的是递归，n为1的时候1种，2的时候2中。其他时候就是 fun(n) = fun(n-1) + fun(n-2);递归的代码很简单。如下
class Solution {public: int climbStairs(int n) { if (n == 0) return 0; if (n == 1) return 1; if (n == 2) return 2; else return climbStairs(n-1) + climbStairs(n-2); }};
但是超时了。看了tag提示DP。于是就分分钟改为DP
class Solution {public: int climbStairs(int n) { if (n == 0) return 0; if (n == 1) return 1; if (n == 2) return 2; vector<int> ans(n); ans[0] = 1; ans[1] = 2; for (int i = 2; i < n; ++i) { ans[i] = ans[i-1] + ans[i-2]; } return ans[n-1]; }};
果断AC。
leetcode Climbing Stairs
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。