跳台阶扩展问题

[编程题]跳台阶扩展问题

热度指数：12673 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

数据范围： $1 \le n \le 20$
进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(1)$

输入描述:

本题输入仅一行，即一个整数 n

输出描述:

输出跳上 n 级台阶的跳法

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

JavaScript V8

怕浪猫

递归

function skip(x) {
  if(x == 1) return 1
  return 2 * skip(x - 1)
}
console.log(skip(readline()));

动态规划

function skip(x) {
  let dp = Array(x + 1).fill(0);
  if (x == 1) return 1;
  if (x == 2) return 2;
  dp[0] = 1;
  dp[1] = 1;
  dp[2] = 2;
  for (let i = 3; i < x + 1; i++) {
    for (let j = 0; j < i; j++) {
      dp[i] += dp[j];
    }
  }
  return dp[x];
}
let n = parseInt(readline());
console.log(skip(n));

发表于 2022-08-31 00:25:05 回复(0)