[動态規劃]DP2 跳台階-簡單

​​DP2 跳台階​​

描述

一隻青蛙一次可以跳上1級台階，也可以跳上2級。求該青蛙跳上一個 n 級的台階總共有多少種跳法（先後次序不同算不同的結果）。

資料範圍：

要求：時間複雜度： ，空間複雜度： 

輸入描述：

本題輸入僅一行，即一個整數 n

輸出描述：

輸出跳上 n 級台階有多少種跳法

示例1

輸入：

2      

輸出：

2      

說明：

青蛙要跳上兩級台階有兩種跳法，分别是：先跳一級，再跳一級或者直接跳兩級。是以答案為2      

示例2

7      

21      

題解

#include <bits/stdc++.h>

int solve(int n)
{
  if (n <= 2)
  {
    return n;
  }
  return solve(n - 1) + solve(n - 2);
}

int main()
{
  int n;
  std::cin >> n;
  std::cout << solve(n) << std::endl;
  return 0;
}