Leetcoder Day34| 动态规划part01

2024-03-02 18:20

本文主要是介绍Leetcoder Day34| 动态规划part01,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

动态规划理论基础

什么是动态规划

动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。

所以动态规划的每一个状态一定是从上一个状态推导出来的,这一点有别于贪心算法,贪心是从局部直接选择最优,不需要推导。

比如背包问题:有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。

贪心算法思路:每次拿物品选一个最大的或者最小的就完事了,和上一个状态没有关系。

动态规划思路:dp[j]是由dp[j-weight[i]]推导出来的,然后取max(dp[j], dp[j - weight[i]] + value[i])。

动态规划的解题步骤

一共有五部曲:

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

要先确定递推公式,然后在考虑初始化,因为一些情况是递推公式决定了dp数组如何初始化。

动态规划应该如何debug

写动规题目,代码出问题很正常!

找问题的最好方式就是把dp数组打印出来,看看究竟是不是按照自己思路推导的!

一些同学对于dp的学习是黑盒的状态,就是不清楚dp数组的含义,不懂为什么这么初始化,递推公式背下来了,遍历顺序靠习惯就是这么写的,然后一鼓作气写出代码,如果代码能通过万事大吉,通过不了的话就凭感觉改一改。这是一个很不好的习惯!

做动规的题目,写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍,心中有数,确定最后推出的是想要的结果

然后再写代码,如果代码没通过就打印dp数组,看看是不是和自己预先推导的哪里不一样。

如果打印出来和自己预先模拟推导是一样的,那么就是自己的递归公式、初始化或者遍历顺序有问题

如果和自己预先模拟推导的不一样,那么就是代码实现细节有问题。

这样才是一个完整的思考过程,而不是一旦代码出问题,就毫无头绪的东改改西改改,最后过不了,或者说是稀里糊涂的过了。

可以自己先思考这三个问题:

  • 这道题目我举例推导状态转移公式了么?
  • 我打印dp数组的日志了么?
  • 打印出来了dp数组和我想的一样么?

509. 斐波那契数

斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1 给你n ,请计算 F(n) 。

示例 1:

  • 输入:2
  • 输出:1
  • 解释:F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2:

  • 输入:3
  • 输出:2
  • 解释:F(3) = F(2) + F(1) = 1 + 1 = 2

按照动态规划5部曲:

  1. 确定dp数组(dp table)以及下标的含义:第i个数的斐波那契数值是dp[i]
  2. 确定递推公式:题目中已经给出,dp[i]=dp[i-1]+dp[i-2]
  3. dp数组如何初始化:题目中把如何初始化也直接给我们了:dp[0] = 0;dp[1] = 1;
  4. 确定遍历顺序:dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历的
  5. 举例推导dp数组:0 1 1 2 3 5 当n=5
class Solution {        public int fib(int n) {if(n<2) return n;int[] dp= new int[n+1];dp[0]=0;dp[1]=1;for(int i=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
}

70. 爬楼梯

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

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

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

示例 1:

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

示例 2:

  • 输入: 3
  • 输出: 3
  • 解释: 有三种方法可以爬到楼顶。
    • 1 阶 + 1 阶 + 1 阶
    • 1 阶 + 2 阶
    • 2 阶 + 1 阶

本题爬到第一层楼梯有一种方法,爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层 ,第二层楼梯再跨一步就到第三层。

  1. 确定dp数组(dp table)以及下标的含义:dp[i]:爬到第i层有dp[i]种方法
  2. 确定递推公式:上i-1层时有dp[i-1]个方法,那么一次走一个台阶,上到第i层时有dp[i]种方法,或者上i-2层时有dp[i-2]个方法,那么一次走两个台阶,上到第i层时有dp[i]种方法。所以此时dp[i]=dp[i-1]+dp[i-2]
  3. dp数组如何初始化:i=1时,dp[1]=1,i=2时,dp[2]=2
  4. 确定遍历顺序:从前向后
  5. 举例推导dp数组:i=5时 1 2 3 5 8
class Solution {/**确定dp数组(dp table)以及下标的含义:dp[i]:爬到第i层有dp[i]种方法确定递推公式:上i-1层时有dp[i-1]个方法,那么一次走一个台阶,上到第i层时有dp[i]种方法,或者上i-2层时有dp[i-2]个方法,那么一次走两个台阶,上到第i层时有dp[i]种方法dp数组如何初始化:i=1时,dp[1]=1,i=2时,dp[2]=2确定遍历顺序:从前向后举例推导dp数组:i=5时 1 2 3 5 8*/public int climbStairs(int n) {if(n<3) return n;int[] dp= new int[n+1];dp[1]=1;dp[2]=2;for(int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
}

746. 使用最小花费爬楼梯

给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1:

输入:cost = [10,15,20]
输出:15
解释:你将从下标为 1 的台阶开始。
- 支付 15 ,向上爬两个台阶,到达楼梯顶部。
总花费为 15 。

示例 2:

输入:cost = [1,100,1,1,1,100,1,1,100,1]
输出:6
解释:你将从下标为 0 的台阶开始。
- 支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。
- 支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。
- 支付 1 ,向上爬一个台阶,到达楼梯顶部。
总花费为 6 

本题要求花费最少,那么有两个要注意的思路:

  • 尽可能多到达花费数少的台阶
  • 尽可能少花钱,也就意味着用更少的次数到达顶层。

从示例2可以看出,每次到达花费为1的台阶花费最少。

并且题设还给出了可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯” 也就是相当于一开始到下标 0或者下标 1 是不花费体力的, 从 下标 0 下标1 开始跳就要花费体力了。

  1. 确定dp数组以及下标的含义:dp[i]:爬到第i层的费用
  2. 确定递推公式:和上一题爬楼梯一样,上到i-1层时花费dp[i-1],那么一次走一个台阶,上到第i层时需要花费dp[i]=dp[i-1]+cost[i-1],或者上i-2层时花费dp[i-2]个方法,那么一次走两个台阶,上到第i层时需要花费dp[i]=dp[i-2]+cost[i-2],所以从i-1还是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数组:本题需要具体情况具体分析

本题还要注意楼层下标是从0开始的,因此顶楼是第cost.lenth层,所以返回和遍历的时候也要算上这一层

class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp = new int[cost.length+1];dp[0]=0;dp[1]=0;for(int i=2; i<=cost.length;i++){ //这里注意是要小于等于,因为需要计算的是顶部n,而花费的长度直到n-1dp[i]=Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);}return dp[cost.length];}
}

这篇关于Leetcoder Day34| 动态规划part01的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/767018

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2

轨迹规划-B样条

B样条究竟是干啥的?白话就是给出一堆点,用样条的方式,给这些点连接起来,并保证丝滑的。 同时B样条分为准均匀和非均匀,以下为准均匀为例。 参考链接1:https://zhuanlan.zhihu.com/p/50626506https://zhuanlan.zhihu.com/p/50626506 参考链接2: https://zhuanlan.zhihu.com/p/536470972h

PMBOK® 第六版 规划进度管理

目录 读后感—PMBOK第六版 目录 规划进度管理主要关注为整个项目期间的进度管理提供指南和方向。以下是两个案例,展示了进度管理中的复杂性和潜在的冲突: 案例一:近期,一个长期合作的客户因政策要求,急需我们为多家医院升级一个小功能。在这个过程中出现了三个主要问题: 在双方确认接口协议后,客户私自修改接口并未通知我们,直到催进度时才发现这个问题关于UI设计的部分,后台开发人员未将其传递给

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划

vue2实践:el-table实现由用户自己控制行数的动态表格

需求 项目中需要提供一个动态表单,如图: 当我点击添加时,便添加一行;点击右边的删除时,便删除这一行。 至少要有一行数据,但是没有上限。 思路 这种每一行的数据固定,但是不定行数的,很容易想到使用el-table来实现,它可以循环读取:data所绑定的数组,来生成行数据,不同的是: 1、table里面的每一个cell,需要放置一个input来支持用户编辑。 2、最后一列放置两个b