[动态规划]BM63 跳台阶-简单

web小门神 lv.1

发布时间：2022-10-20 21:04:56 323

描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：要求：时间复杂度：，空间复杂度：

示例1

输入：

复制返回值：

复制说明：

青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2

示例2

输入：

复制返回值：

题解

假设我们要跳到第i台阶，那么只能从i-1和i-2这两个地方到达。因此如果我们用数组来表示到达第i个台阶的方法数，那么有以下关系：

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

这个公式，实际上和斐波那契数一样，很容易写出代码

动态规划解法

int jumpFloor(int n)
{
  if (n <= 2)
  {
    return n;
  }

  std::vector<int> v(n + 1, 0);
  v[1] = 1;
  v[2] = 2;
  for (int i = 3; i <= n; ++i)
  {
    v[i] = v[i - 1] + v[i - 2];
  }
  return v[n];
}

递归解法

int jumpFloor_r(int n)
{
  if (n == 1)
  {
    return 1;
  }

  if (n == 2)
  {
    return 2;
  }

  return jumpFloor(n - 1) + jumpFloor(n - 2);
}

文章来源： https://blog.51cto.com/u_6650004/5395224

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。