当前位置: 首页 > article >正文

备战秋招60天算法挑战,Day28

题目链接: https://leetcode.cn/problems/climbing-stairs/

视频题解: https://www.bilibili.com/video/BV1h1421t7W3/

LeetCode 70.爬楼梯

题目描述

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

举个例子:

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

视频题解

爬楼梯

思路来源

思路来源

知识回顾

动态规划是一种通过将原问题分解为子问题来求解复杂问题的算法思想。它通常用于求解最优化问题,例如最长公共子序列、背包问题等。动态规划的核心思想是将原问题分解为若干个子问题,通过求解子问题的最优解推导出原问题的最优解。可以通过两点来判断一个问题能不能通过动态规划来解,一是该问题是否存在递归结构,二是对应的子问题能否记忆化。动态规划可以通过带备忘录的自上而下的递归自下而上的迭代来分别实现。由于递归需要用到栈来实现,一些语言对递归的深度是有限制的,所以自下而上的迭代是动态规划的最佳实现方式

思路解析

假设只有4个台阶,0阶代表地面。

整个爬楼梯的过程对应的决策树可以表示成下图:

每个节点的值表示剩余的台阶数,从根节点到叶子结点组成的路径代表一种爬楼梯的方法。

整个决策树存在递归结构,还存在重复子问题两个节点2三个节点1,这些子问题计算一次后可以直接保存下来,避免多次重复计算。这就满足了使用动态规划的条件:存在递归结构子问题可以记忆化。所以本题可以用动态规划来解,动态规划的两个核心点是推导状态转移公式边界处理

定义dp[i]i个台阶对应的爬楼梯的方法个数dp[i]的准确定义是推导状态转移公式的关键。

因为每次只能爬12个台阶,从上面的图可以看出4个台阶的爬楼梯方法可以拆解成32个台阶爬楼梯方法之和。说白了就是节点4到叶子节点0的所有路径等于节点3节点2到叶子节点路径的总和。
d p [ 4 ] = d p [ 3 ] + d p [ 2 ] dp[4] = dp[3] + dp[2] dp[4]=dp[3]+dp[2]

4个台阶进一步扩展到n个台阶,我们得到下面的状态转移公式
d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ] , 1 < i < = n dp[i] = dp[i-1] + dp[i-2], 1 < i <= n dp[i]=dp[i1]+dp[i2],1<i<=n

接下来进行边界处理,根据上面的公式可知 d p [ 2 ] = d p [ 1 ] + d p [ 0 ] dp[2] = dp[1] + dp[0] dp[2]=dp[1]+dp[0],很显然dp[1] = 1dp[2] = 2,上面也说到0阶代表地面,为了写代码方便这里我们定义dp[0] = 1

C++代码

class Solution {
public:
    int climbStairs(int n) {
        //因为有n阶台阶,台阶从0开始计算,所以定义n+1个元素
        vector<int> dp(n+1, 0);
        //定义边界dp[0]=1
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            //状态转移公式
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

java代码

class Solution {
    public int climbStairs(int n) {
        // 因为有n阶台阶,台阶从0开始计算,所以定义n+1个元素
        int[] dp = new int[n + 1];
        // 定义边界dp[0]=1
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            // 状态转移公式
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

python代码

class Solution:
    def climbStairs(self, n: int) -> int:
        # 因为有n阶台阶,台阶从0开始计算,所以定义n+1个元素
        dp = [0] * (n + 1)
        # 定义边界dp[0]=1
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n + 1):
            # 状态转移公式
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

上面的代码实现使用了一个长为n+1dp数组,我们观察状态转移公式的规律,其实并不需要保存每个台阶数为i的爬楼梯方法,可以通过两个整型变量来优化上面的实现。

c++代码

class Solution {
public:
    int climbStairs(int n) {
        int pre = 1;
        int next = 1;
        for (int i = 2; i <= n; ++i) {
            int temp = next;
            next = pre + next;
            pre = temp;
        }
        return next;
    }
};

java代码

class Solution {
    public int climbStairs(int n) {
        int pre = 1;
        int next = 1;
        for (int i = 2; i <= n; ++i) {
            int temp = next;
            next = pre + next;
            pre = temp;
        }
        return next;
    }
}

python代码

class Solution:
    def climbStairs(self, n: int) -> int:
        pre = 1
        next = 1
        for i in range(2, n + 1):
            temp = next
            next = pre + next
            pre = temp
        return next

复杂度分析

时间复杂度: 两种实现方式的时间复杂度都是O(n)n为台阶的个数。

空间复杂度: 第一种实现方式的空间复杂度为O(n)n为台阶的个数。第二种实现方式的空间复杂度为O(1)


http://www.kler.cn/news/283736.html

相关文章:

  • 个人旅游网(1)——数据库表详解
  • 爬虫入门学习
  • Java Web —— 第十天(AOP切面编程)
  • Dxf文件中多段线弧线的计算
  • 三星与海力士发力决战HBM4
  • 【知识】缓存类型和策略
  • 数据合规性分析:守护信息安全的关键防线
  • 原生开发柱状图
  • 钉钉好用吗?类似钉钉的内部知识库有哪些?
  • 【微信小程序】微信小程序如何使用 MobX 进行状态管理?
  • 【已解决】win11笔记本电脑突然无法检测到其他显示器 / 无法使用扩展屏(2024.8.29 / 驱动更新问题)
  • Linux使用ifconfig配置临时ip地址
  • ET6框架(八)事件系统
  • UE5 摄像机图像采集到材质 映射到 UI 和 物体表面
  • C语言内存操作函数
  • gitee版本控制
  • 记录|如何全局监听鼠标和键盘等事件
  • ARCGIS 纸质小班XY坐标转电子要素面(2)
  • JavaScript中DOW和BOW;笔记分享;知识回顾
  • YOLOv9改进策略【模型轻量化】| PP-LCnet
  • 代码随想录算法训练营第五十八天 | 图论part08
  • 验证码获取测试的步骤和要点
  • nipplejs(虚拟游戏操作杆)跟fabric(canvas缩放、旋转)
  • 解决linux每次打开新终端都要重新source ~/.bashrc问题
  • word文档转html(只支持段落和表格)
  • git 拉取或推送到指定分支
  • IPython 使用技巧整理
  • nginx启动报错:worker_connections exceed open file resource limit: 1024
  • ES6基础----Map的使用
  • 【问题分析】CtsWindowManagerDeviceAnimations【Android15】