day38|动态规划-爬楼梯问题

这篇具有很好参考价值的文章主要介绍了day38|动态规划-爬楼梯问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

DP问题类型:

动态规划比较重要的是找到前后两个状态之间的联系,在向后遍历的过程中注意遍历的顺序和初始化操作。
动归基础类问题
背包问题
打家劫舍
股票问题
子序列问题

DP问题的一些注意事项:

动态规划类的问题代码都是比较简洁的,按照dp打印逻辑观察打印出来的数值。

  1. dp数组以及下标的含义dp[i][j],dp[i]
  2. 递推公式
  3. dp数组的初始化,有时候初始化成1,有时候初始化成0,有时候从某个下标开始初始化成1
  4. 遍历顺序:两层for循环的顺序是怎样的
  5. 打印dp数组:纠正动态规划的问题

509. 斐波那契数

复习动归五部曲:
dp数组-初始化-递推公式-遍历顺序-打印dp数组
入门级别的问题
day38|动态规划-爬楼梯问题

class Solution:
    def fib(self, n: int) -> int:
        # 递归解法
        def r(n):
            if n == 0 : return 0
            if n == 1 : return 1
            return r(n-1) + r(n-2)
        return r(n)

        '''
        # 动态规划方法
        dp = [0] * (n+1)
        if n == 0 : return 0
        if n == 1 : return 1
        dp[0] = 0
        dp[1] = 1
        for i in range(2,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[-1]
        '''
    

        ''' # 一般方法
        if n == 0: return 0
        if n == 1: return 1
        cur = 1
        pre = 0
        i = 2
        while i<=n:
            temp = cur
            cur = pre + cur
            pre = temp
            i += 1
        return cur
        '''

70. 爬楼梯

核心思路: 第i个台阶收到前1个台阶和倒数第二个台阶影响
问题的思考方式是先那几个进行举例,然后找到其中的规律。三阶可以用一阶和二阶楼梯进行推导。
dp五部曲进行思考:

  1. 确定dp[i]含义:第i个台阶的上楼的种类
  2. 递推公式:dp[i] = dp[i-1] + dp[i-2]
  3. 数组的初始化:dp[0] = 0 dp[1] = 1
  4. 遍历方式:从前往后
  5. 打印dp数组
class Solution:
    def climbStairs(self, n: int) -> int:
        # 当前楼梯走几步受到之前两个台阶的影响。
        # 根据dp五部曲进行求解
        dp = [0] * (n+1)
        if n == 0: return 0
        if n == 1: return 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]

746. 使用最小花费爬楼梯

有两个数组cost[i],当前台阶的花费受到前两个台阶花费的影响。
dp五步曲进行思考:文章来源地址https://www.toymoban.com/news/detail-466425.html

  1. dp[i]含义:第i个台阶的最小花费
  2. 递推公式:dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
  3. dp数组的初始化:dp[0] = 0,dp[1] = 0
  4. 遍历方式:从前往后
  5. 打印dp数组
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0]*(len(cost)+1)
        if len(cost) <=1 : return 0
        dp[0] = 0
        dp[1] = 0
        for i in range(2,len(cost)+1):
            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
        return dp[len(cost)]

到了这里,关于day38|动态规划-爬楼梯问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法记录 | Day38 动态规划

    对于动态规划问题,将拆解为如下五步曲 确定dp数组(dp table)以及下标的含义 确定递推公式 dp数组如何初始化 确定遍历顺序 举例推导dp数组 思路: 确定dp数组(dp table)以及下标的含义:dp[i]的定义为:第i个数的斐波那契数值是dp[i] 确定递推公式:状态转移方程 dp[i] = dp

    2023年04月22日
    浏览(42)
  • DAY42:动态规划(二)斐波那契数列+爬楼梯+最小花费爬楼梯

    斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: 给定 n ,请计算 F(n) 。 示例 1: 示例 2: 示例 3: 提示: 0 = n = 30 思路:动规五步 确定dp数组和数组下标含义 DP题目都需要定义一维

    2024年02月13日
    浏览(56)
  • 代码随想录 day38 第九章 动态规划part01

    ●  理论基础 ●  509. 斐波那契数 ●  70. 爬楼梯 ●  746. 使用最小花费爬楼梯 理论基础 解决动态规划必须要想清楚的点 dp数组以及下标的含义 递推公式 dp数组如何初始化 遍历顺序 打印数组 检查结果 关联 leetcode 509. 斐波那契数 思路 动规五部曲 dp数组以及下标的含义

    2024年04月17日
    浏览(48)
  • 【Day45】代码随想录之动态规划part7—爬楼梯(进阶)、零钱兑换、完全平方数

    今天又是补打卡的一天,开冲!!! 今日任务: 70.爬楼梯(进阶) 322.零钱兑换 279.完全平方数 这道题之前做过一次,但是可以采用完全背包的问题来分析一遍。 卡玛网题目:【57.爬楼梯】 这个题目其实是更难了一点,因为前面的题目都是每次要不爬1阶楼梯,要不爬2阶楼

    2024年03月25日
    浏览(52)
  • 算法 DAY45 动态规划07 70. 爬楼梯 322. 零钱兑换 279. 完全平方数 139. 单词拆分 多重背包

    和377. 组合总和 Ⅳ (opens new window)基本就是一道题了。 本题代码不长,题目也很普通,但稍稍一进阶就可以考察完全背包 动态规划五部曲 1、确定dp[j]的含义 dp[j] 凑成 j 的最少硬币的个数 2、确定递推公式 比如想凑成3, 如果手里有1,那么最小个数就是dp[2]+1 如果手里有2,那

    2024年02月02日
    浏览(59)
  • java算法day45 | 动态规划part07 ● 70. 爬楼梯 (进阶) ● 322. 零钱兑换 ● 279.完全平方数

    题目描述: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 = m n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 输入描述:输入共一行,包含两个正整数,分别表示n, m 输出描述:输出一个整数,表示爬到楼顶的方法数

    2024年04月14日
    浏览(54)
  • 代码随想录Day32 动态规划01 LeetCodeT509 斐波那契数列 T70 爬楼梯 T746 爬楼梯的最小消耗

    动态规划首先可以解决的问题有背包问题,打家劫舍问题,股票问题,子序列问题等,主要是将一个大的问题切分成多个重叠的子问题,所以动态规划一定是上一个状态递推过来的,有一个重要的 状态转移方程, 但是这也并不是解题的全部,我们将动态规划的题目基本分为五步来完成

    2024年02月06日
    浏览(68)
  • Java之动态规划之爬楼梯问题

    目录 0.动态规划问题 一.爬楼梯 1.题目描述 2.问题分析 3.代码实现 二.使用最小花费爬楼梯 1.题目描述 2.问题分析 3.代码实现 三. 爬楼梯(进阶版) 1.题目描述 2.问题分析 3.代码实现 四.坏掉楼梯的爬楼梯问题 1.题目描述 2.问题分析 3.代码实现 五.第39级台阶 1.题目描述 2.问题分析

    2024年02月08日
    浏览(45)
  • 算法打卡day39|动态规划篇07| Leetcode 70. 爬楼梯(进阶版)、322. 零钱兑换、279.完全平方数

    Leetcode 70. 爬楼梯(进阶版) 题目: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 = m n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 输入描述:输入共一行,包含两个正整数,分别表示n, m 输出描述:输出一个整数,

    2024年04月14日
    浏览(65)
  • 爬楼梯问题-从暴力递归到动态规划(java)

    一个总共N 阶的楼梯(N 0) 每次只能上一阶或者两阶。问总共有多少种爬楼方式。 示例1: N = 1, 一步上去了,返回1. 示例2: N = 2时。 可以第一次上一阶,再上一阶,这是一种方式, 也可以一次直接上两阶,这也是一种方式, 返回 2; 示例3: N = 3: 可以选择, 1 1 1, 1

    2024年02月10日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包