您现在的位置是:首页 > 正文

LeetCode爬楼梯

2024-02-01 02:58:47阅读 2

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

示例 1:

输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2:

输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
4. 1 阶 + 1 阶 + 1 阶
5. 1 阶 + 2 阶
6. 2 阶 + 1 阶

这道题最简单的方法是利用斐波那契数列来计算

var climbStairs = function(n) {
    if (n === 1 || n === 2) {
             return n;
        }
    let number = climbStairs(n - 1) + climbStairs(n - 2);
    return number;
}

但是这么做在n为46的时候在LeetCode中会递归超时
所以对动态规划进行优化

用一个数组 dp 存放中间子问题的结果。
定义dp[i]:爬 i 级楼梯的方式数。从base case: dp[0], dp[1]出发,顺序计算,直到算出dp[i]

const climbStairs = (n) => {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i < dp.length; i++) {
    dp[i] = dp[i - 2] + dp[i - 1];
  }
  return dp[n];
}
const dp = new Array(n + 1).fill(0);

这句话中,new Array(n + 1)创建了一个数组里面有n+1个数
new Array(n + 1).fill(0);表示里面的数都用0替代,如果不写0则都是undefined
n + 1如果变为n ,n = 2 的时候会报错

网站文章

  • 解决docker中/etc/default/docker配置DOCKER_OPTS 失效问题

    docker安装在桌面版ubuntu的时候,默认的配置文件/etc/default/docker 里的配置是无效的(14.04 server版并无问题),导致之前的很多工作进展缓慢,这个问题在官方文档中有出现,但是在安装步骤中,不循着问题根本找不到,非常坑爹。 解决办法是:打开/lib/systemd/system/docker.service 文件 添加一行 EnvironmentF

    2024-02-01 02:58:19
  • Python asyncio异步编程常见问题

    Python asyncio异步编程常见问题

    今天继续给大家介绍Python相关知识,本文主要内容是Python asyncio异步编程常见问题。一、asyncio编程简单示例二、asyncio编程常见问题三、报错原因及解决方案

    2024-02-01 02:58:12
  • L2-033 简单计算器(Python3)

    L2-033 简单计算器(Python3)

    团体程序设计天梯赛-练习集

    2024-02-01 02:58:06
  • 基于CART树的银行贷款风控模型实现

    基于CART树的银行贷款风控模型实现

    基于CART树的银行贷款风控模型实现

    2024-02-01 02:57:36
  • 服务器系统吞吐量是否就是带宽,【经验分享】Iperf测试网络吞吐量的方法

    服务器系统吞吐量是否就是带宽,【经验分享】Iperf测试网络吞吐量的方法

    Iperf测试:使用udp设定带宽2M,5M,10M,同时观察对正进行的ping测试的影响。证明iperf使用udp测试/使用一定或最大带宽时,同样能影响tcp协议的流量。任务(1) (使用UDP,参数-u -b 2M)设定不同带宽#iperf3-c192.168.199.18-p54321-i1-t1800-u-b1M(2) 双向同时测试(在任一端多开一个iperf por...

    2024-02-01 02:57:29
  • 阿里云ECS最新的实例规格族有哪些

    阿里云ECS最新的实例规格族有哪些

    通过本文您可以了解目前阿里云在售的所有ECS实例规格族的信息,包括每种规格族的特点,适用场景,以及如何选择符合自己需求的实例规格族。 什么是阿里云ECS实例 实例是能够为您的业务提供计算服务的最小单位,它是以一定的规格来为您提供相应的计算能力的。 根据业务场景和使用场景,ECS实例可以分为多种规格族。同一个规格族里,根据CPU和内...

    2024-02-01 02:57:22
  • android shell hello world,Android Framework 之HelloWorld(三)

    本来是要写一个linux驱动,用于控制led灯的,但考虑到nanopc-T4的内核已经帮我们配置好设备树,已经可以利用/sys/class/gpio操作gpio了,所以没必要再造轮子了!在shell里,可以利用下面的命令控制Led灯的亮与灭:#导出GPIO0_A0管脚echo 32 > /sys/class/gpio/export#让GPIO0_A0管脚作为输出使用echoout >...

    2024-02-01 02:56:52
  • ACM题目里求组合数C(n,m)的方法

    (212条消息) 组合数c(n,m)计算的四种方法_wjl_zyl_1314的博客-CSDN博客_c计算组合数static long[][] longs=new long[2000][1000];//...

    2024-02-01 02:56:43
  • 执行Django 的迁移命令报错[1193, Unknown system variable default_storage_engine]

    执行Django 的迁移命令报错[1193, Unknown system variable default_storage_engine]

    执行Django 的迁移命令报错[1193, Unknown system variable default_storage_engine]

    2024-02-01 02:56:36
  • Android随机点名器,Excel基础知识-详解随机点名器

    Android随机点名器,Excel基础知识-详解随机点名器

    说道制作个案例纯粹意外,我多少有点选择恐惧症,为了不在“选择”上纠结,就自己小玩了一下,就用了程序做了个选择器,其实很简单,就是有小时候玩的“点兵点将",稍微变化就成今天的案例!我一直的原则是用最少的...

    2024-02-01 02:56:30