[动态规划]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;
}