程序员必学算法「动态规划」:爬楼梯(完全背包解法)

原创代码随想录2021-02-02 08:35:00

通知:我将公众号文章和学习相关的资料整理到了Github :https://github.com/youngyangyang04/leetcode-master,方便大家在电脑上学习,可以fork到自己仓库,顺便也给个star支持一波吧!

之前讲这道题目的时候,因为还没有讲背包问题,所以就只是讲了一下爬楼梯最直接的动规方法(斐波那契)。

这次终于讲到了背包问题,我选择带录友们再爬一次楼梯!

此情此景,借用一下《无间道》的台词 哈哈哈。

70. 爬楼梯

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

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1:
输入:2
输出:2
解释:有两种方法可以爬到楼顶。

  1. 1 阶 1 阶

  2. 2 阶

示例 2:
输入:3
输出:3
解释:有三种方法可以爬到楼顶。

  1. 1 阶 1 阶 1 阶

  2. 1 阶 2 阶

  3. 2 阶 1 阶

思路

这道题目 我们在动态规划:爬楼梯 中已经讲过一次了,原题其实是一道简单动规的题目。

既然这么简单为什么还要讲呢,其实本题稍加改动就是一道面试好题。

改为:每次可以爬 1 、 2或者m 个台阶。问有多少种不同的方法可以爬到楼顶呢?

1阶,2阶,m阶就是物品,楼顶就是背包。

每一阶可以重复使用,例如跳了1阶,还可以继续跳1阶。

问跳到楼顶有几种方法其实就是问装满背包有几种方法。

此时大家应该发现这就是一个完全背包问题了!

和昨天的题目动态规划:377. 组合总和 Ⅳ基本就是一道题了。

动规五部曲分析如下:

  1. 确定dp数组以及下标的含义

dp[i]:爬到有i个台阶的楼顶,有dp[i]种方法

  1. 确定递推公式

动态规划:494.目标和动态规划:518.零钱兑换II动态规划:377. 组合总和 Ⅳ中我们都讲过了,求装满背包有几种方法,递推公式一般都是dp[i] = dp[i - nums[j]];

本题呢,dp[i]有几种来源,dp[i - 1],dp[i - 2],dp[i - 3] 等等,即:dp[i - j]

那么递推公式为:dp[i] = dp[i - j]

  1. dp数组如何初始化

既然递归公式是 dp[i] = dp[i - j],那么dp[0] 一定为1,dp[0]是递归中一切数值的基础所在,如果dp[0]是0的话,其他数值都是0了。

下标非0的dp[i]初始化为0,因为dp[i]是靠dp[i-j]累计上来的,dp[i]本身为0这样才不会影响结果

  1. 确定遍历顺序

这是背包里求排列问题,即:1、2 步 和 2、1 步都是上三个台阶,但是这两种方法不!

所以需将target放在外循环,将nums放在内循环。

每一步可以走多次,这是完全背包,内循环需要从前向后遍历。

  1. 举例来推导dp数组

介于本题和动态规划:377. 组合总和 Ⅳ几乎是一样的,这里我就不再重复举例了。

以上分析完毕,C 代码如下:

class Solution {public:    int climbStairs(int n) {        vector<int> dp(n   1, 0);        dp[0] = 1;        for (int i = 1; i <= n; i ) { // 遍历背包            for (int j = 1; j <= m; j ) { // 遍历物品                if (i - j >= 0) dp[i]  = dp[i - j];            }        }        return dp[n];    }};

代码中m表示最多可以爬m个台阶,代码中把m改成2就是本题70.爬楼梯可以AC的代码了。

总结

本题看起来是一道简单题目,稍稍进阶一下其实就是一个完全背包!

如果我来面试的话,我就会先给候选人出一个 本题原题,看其表现,如果顺利写出来,进而在要求每次可以爬[1 - m]个台阶应该怎么写。

顺便再考察一下两个for循环的嵌套顺序,为什么target放外面,nums放里面。

这就能考察对背包问题本质的掌握程度,候选人是不是刷题背公式,一眼就看出来了。

这么一连套下来,如果候选人都能答出来,相信任何一位面试官都是非常满意的。

本题代码不长,题目也很普通,但稍稍一进阶就可以考察完全背包,而且题目进阶的内容在leetcode上并没有原题,一定程度上就可以排除掉刷题党了,简直是面试题目的绝佳选择!

力扣刷题指南:https://github.com/youngyangyang04/leetcode-master

(0)

相关推荐

  • 经典动态规划:0-1 背包问题

    前言 经过前面三篇动态规划文章的介绍,相信大家对动态规划.分治.贪心有了充分的理解,对动态规划的 3 个核心问题.其本质也有了了解. 纸上得来终觉浅,绝知此事要躬行. 那么今天开始我们来聊聊具体的那些 ...

  • 剑指 Offer 14- I. 剪绳子

    我服了.动态规划杀我. 可以说一说解决动态规划的思路(只做了两三道就总结了emmm) 1.识别动态规划问题 --重叠子问题:大问题可以分为一个个子问题.和分治策略分割的子问题不同(分治问题的子问题是相 ...

  • 动态规划(DP)

    本课程是从少年编程网转载的课程,目标是向中学生详细介绍计算机比赛涉及的编程语言,数据结构和算法.编程学习最好使用计算机,请登陆 www.3dian14.org (免费注册,免费学习). 本月7月13日 ...

  • ​LeetCode刷题实战264:丑数 II

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • 这个前端竟然用动态规划写瀑布流布局?给我打死他!

    前言 瀑布流布局是前端领域中一个很常见的需求,由于图片的高度是不一致的,所以在多列布局中默认布局下很难获得满意的排列. 我们的需求是,图片高度不规律的情况下,在两列布局中,让左右两侧的图片总高度尽可能 ...

  • Python | 动态规划解决“返回第n个丑数”

    问题描述给你一个整数 n ,请你找出并返回第 n 个 丑数 .丑数 就是只包含质因数 2.3 和/或 5 的正整数.示例 1:输入:n = 10输出:12解释:[1, 2, 3, 4, 5, 6, 8 ...

  • 一文搞懂什么是递归,程序员必会算法之一

    前言 今天我们来讲讲递归算法,递归在我们日常工作中是比较常见且常用的算法,面试中面试官也经常会让我们手写递归算法.由此可见递归算法的重要性. 递归 什么是递归 简单来说递归就是方法自己调用自己,每次调 ...

  • 「干货总结」程序员必知必会的十大排序算法

    身为程序员,十大排序是是所有合格程序员所必备和掌握的,并且热门的算法比如快排.归并排序还可能问的比较细致,对算法性能和复杂度的掌握有要求.bigsai作为一个负责任的Java和数据结构与算法方向的小博 ...

  • 「程序员必看」超详细的Python文件操作知识

    本文分七个模块为大家详细介绍python中文件操纵相关知识,闲话少说,让我们开始! 一.文件的打开和关闭 open()函数 f1 = open(r'd:\测试文件.txt', mode='r', en ...

  • 人人必学的「海姆立克急救法」,转给家人一起学!

    人人必学的「海姆立克急救法」,转给家人一起学!

  • 程序员必须练就的「性能调优」组合拳【2】

    性能调优系列前序文章索引: 程序员必须掌握的性能调优:老兵哥结合个人经历解释了程序员往架构师方向发展时为什么要跨越性能调优这一关,以及介绍了从 X.Y.Z 三个维度优化性能的思路. 从  X  维度优 ...

  • 程序员必须练就的「性能调优」组合拳【1】

    在[ 程序员必须掌握的性能调优 XYZ ]这篇文章中,老兵哥结合个人经历解释了程序员往架构师方向发展时为什么要跨越性能调优这一关,这是我们建立流程化.结构化.系统化的思维的契机.另外,老兵哥还介绍了从 ...

  • 练声必学的「吐字归音」究竟怎么掌握?我一次整理了这5点,看到就是赚到!

    - 这是 梨花声优基地 推送的第157篇文章 - 嗨,这里是关心你成长变现的小梨花~ 最近,有学员在后台咨询我:每次朗读作业,都被讲师评价"吐字归音不正确",该怎么办? 有些同学看 ...

  • 程序员必知必会10大基础算法

    来源:博客园 链接: http://kb.cnblogs.com/page/210687/ 算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法.在平均状况下,排序n个项目要Ο(nlogn ...

  • 韩式蛋糕裱花必学的「意式奶油霜」

    [意式奶油霜材料] 发酵黄油125g/糖(1)25g/糖(2)25g/水15g/蛋白45g [调味] 香草精华适量(可选) [做法] 1.黄油切小块室温软化,用刮刀搅至顺滑备用 2.蛋白分次加入糖(1 ...