LeetCode70——Climbing Stairs

喜欢ヅ旅行 2022-08-09 17:47 236阅读 0赞

LeetCode70——Climbing Stairs

题意：

爬楼梯你可以爬一步或者两步，求你到终点时有多少种可能。

首先假设终点是3

则你可以：

1.先跳两步再跳一步

2.先跳一步再跳两步

3.先跳一步，再跳一步，再跳一步。

1和3这两种情况都要经过第二个台阶。

第2种情况要经过第一个台阶。

那么到达第3个台阶需要可能的组合就是3种，分别是经过第1级台阶和经过第2级台阶的个数的和。

根据此，推断写出动归方程：

dp[i] = dp[i-1] + dp[i-2]

虽然说不清为什么，但这就是一个斐波那契数列的递推关系。。。

代码：

  1. class Solution {
  2. private:
  3.     void helper(vector<int>&dp,int n)
  4.     {
  5.         int i = 3;
  6.         while (i <= n)
  7.         {
  8.             dp[i] = dp[i - 1] + dp[i - 2];
  9.             i++;
  10.         }
  11.     }
  12. public:
  13.     int climbStairs(int n) {
  14.         vector<int>dp(n+1);
  15.         dp[0] = 0;
  16.         dp[1] = 1;
  17.         dp[2] = 2;
  18.         helper(dp, n);
  19.         return dp[n];
  20.     }
  21. };

发表评论

表情：
评论列表 （有 0 条评论，236人围观）

还没有评论，来说两句吧...

相关阅读