day44代码训练|动态规划part06

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

完全背包和01背包问题唯一不同的地方就是,每种物品有无限件

1. dp数组的含义

dp[i][j] 0-i物品,重量为j的容量时,最大的价值

2. 递推公式

dp[i][j] = max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);

两种状态,不用物品i的话,直接是用dp[i-1][j]

选用物品的话,为了重复使用物品i,其实是dp[i][j-weight[i]]+value[i],因为对dp[i][...]都是仍有机会再次使用物品i得

3.初始化dp[...][0]=0 由于重量为0,不可能有价值

dp[0][...] dp[0][j] = dp[0][j-wi]+vi;

4. 遍历顺序

物品和背包在外循环都可以(因为是二维),对背包空间需要是正向遍历,因为需要同行的前面的数据

压缩为1维dp:

把二维dp压缩为一行滚动更新//把dp[i-1]拷贝到dp[i]上

1. dp数组的含义

dp[j]重量为j的容量时,最大的价值

2. 递推公式

dp[j] = max([j],dp[j-weight[i]]+value[i]);

两种状态,不用物品i的话,直接是用dp[i-1][j]

3.初始化

dp[0]=0;(背包没有任何空间)

其他也初始化为0(非负的最小值),不会影响循环中的更新(需要用max,如果初始值太大,会影响递推公式)

4. 遍历顺序

根据递推公式:必须要正向遍历背包,因为在二维的角度看,会用到同一行,之前的数据

压缩来看:当前的数据更新 只需要dp[j-wi]+vi <--> dp[i][j-wi]+vi(由于正向遍历,在遍历到当前位置的时候,已经在一维dp数组中在当前位置的前方《0,j-1》全部更新了dp[i]层的数据,而当前j位置及以后仍然是dp[i-1]层数据),和dp[j] <->dp[i-1][j](其实就是上一层遍历储存在dp[i-1]层的数据)

而背包与物品的循环内外层关系并不重要了

对于01背包问题

如果倒序遍历背包,然后背包循环还在外面的话,dp[j-w]还在初始化状态时,就把dp[j]从0层到i层更新完了,(最终只会装入一个物品,当前容量下能装下的某一个物品且其价值最大)

所以必须先遍历物品,再对每个物品进行背包空间上的倒序遍历,这样在对第i层的dp[j]进行递推的时候,dp[j-wi]并不是初始化的值,而是已经计算过第i-1层的值了

对于完全背包问题

如果是正序的话,不论先遍历背包还是先遍历物品

在递推更新dp[j] 的时候需要的

dp[i] = max(dp[j],dp[j-weight[i]]+value[i]); dp[j]对应第i-1层 dp[j-wi]对应第N层(N 为物品个数),是提前算好的数据,但是由于是取最值,所以第N层的dp[j-wi]也是可以的,只要最后是整体的最大值就行了。与顺序无关。所以及时使用之后的数据也不影响最后的结果

举例:

重量         价值
物品0 1 15
物品1 3 60
物品2 4 30

先物品再背包

背包体积 0 1 2 3 4
物品0 0 15 30 45 60
物品1 0 15 30 60 75
物品2 0 15 30 60 75

先背包再物品

背包体积 0 1 2 3 4
物品0 0 15 30 45 75
物品1 0 15 30 60
物品2 0 15 30 60

其实遍历下来跟二维dp还是有所不同因为在更新dp[j=4] (dp[i=0][j=4])的时候本来应该应用dp[i=0][j=3]+v1来跟0比较大小,但是先背包再物品的遍历顺序让当时的dp[j=3]其实是dp[i=2][j=3],所以dp[j=4]在i=0的时候已经是75了,但是并不影响,因为我们要取的是最大值,什么顺序,什么时候最大,并不影响最后结果,所以可以改变循环顺序

但是后面一题跟顺序有关,就不能随意改变循环顺序了

518.零钱兑换II

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

由于是求组合数,所以跟顺序没有关系

例如示例:

5 = 2 + 2 + 1

5 = 2 + 1 + 2

这是一种组合,都是 2 2 1。

1. dp 数组及含义

2维:dp[i][j] 的定义如下:

若只使用前 i 个物品(可以重复使用),当背包容量为 j 时,有 dp[i][j] 种组合方法可以装满背包

1维:dp[j]:凑成总金额j的货币组合数为dp[j]

2. 递推公式

2维

如果你不把这第 i 个物品装入背包,也就是说你不使用 coins[i-1] 这个面值的硬币,那么凑出面额 j 的方法数 dp[i][j] 应该等于 dp[i-1][j],继承之前的结果。

如果你把这第 i 个物品装入了背包,也就是说你使用 coins[i-1] 这个面值的硬币,那么 dp[i][j] 应该等于 dp[i][j-coins[i-1]]

dp[i][j] = dp[i - 1][j]  + dp[i][j-coins[i-1]];

1维:

dp[j] += dp[j - nums[i]];

3. 初始化

2维:base case 为 dp[0][..] = 0, dp[..][0] = 1。i = 0 代表不使用任何硬币面值,这种情况下显然无法凑出任何金额;j = 0 代表需要凑出的目标金额为 0,那么什么都不做就是唯一的一种凑法。

1维:dp[..][0] = 1由此可得之:

dp[j=0]=1; (目标为0的时候什么都不放就是一种方法)

由2维的 dp[0][..] = 0也可以看出,其他dp[j]初始化为0 对1维递推公式来说也是,初始化为0才不会影响累加公式的结果

4. 遍历顺序:

2维:背包正序遍历即可

两个循环内外部影响

1维:

先物品再背包,公式计算时是:dp[j]<-> dp[i][j]=dp[j]<->dp[i-1][j]+ dp[j - nums[i]]<->dp[i][j-nums[i]]

可以跟2维公式对应上

如果先循环背包再循环物品,从某点开始,dp[j-nums[i]]本应该对应2维的dp[i][j-nums[i]]却对应的是dp[N][j-nums[i]],因为递推公式是累加,之后的结果都会相应跟二维dp数组发生越来越大的结果

dp[j]<-> dp[i][j]=dp[j]<->无法对应+ dp[j - nums[i]]<->无法对应

不同遍历方式一维dp数组打印:

例子:

  • 输入: amount = 5, coins = [1, 2, 5]

先物品再背包

0 1 2 3 4 5
c1 1 1 1 1 1 1
c2 1 1 2 2 3 3
c5 1 1 2 2 3 4

day44代码训练|动态规划part06,动态规划,算法

先背包再物品

0 1 2 3 4 5
c1 1 1 1 2 3 5
c2 1 1 2 3 5 8
c5 1 1 2 3 5 9

day44代码训练|动态规划part06,动态规划,算法

另一种理解方式:来源代码随想录

day44代码训练|动态规划part06,动态规划,算法

377. 组合总和 Ⅳ

其实本体本质不是一个完全背包问题,可以直接立即为:

每次能走1-n步的爬楼梯有多少种方法的问题

理解维爬楼梯问题后,可以简单直观的看出,我们必须先遍历到了第几层楼梯

再循环遍历这次爬几阶楼梯,这样每次dp[j]都讨论了会选择之前不同爬楼梯阶数的可能性dp[j]+=dp[j-nums[i]],所以其实把排列/顺序已经考虑在了其中

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0]=1;
        for(int j=0;j<=target;j++){
            for(int i=0;i<nums.length;i++){
                if(j>=nums[i])dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[target];
    }
}

如果要用二维来理解:如下:

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

day44代码训练|动态规划part06,动态规划,算法

day44代码训练|动态规划part06,动态规划,算法文章来源地址https://www.toymoban.com/news/detail-770905.html

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

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

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

相关文章

  • day48算法训练|动态规划part09

    1. dp数组(dp table)以及下标的含义 dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i] 。 2.递推公式 决定dp[i]的因素就是第i房间偷还是不偷。 如果偷第i房间,那么dp[i] = dp[i - 2] + nums[i] ,即:第i-1房一定是不考虑的,找出 下标i-2(包括i-2)以内的房屋,最多

    2024年01月16日
    浏览(42)
  • 代码随想录算法训练51 | 动态规划part12

    本题加了一个冷冻期,状态就多了,有点难度,大家要把各个状态分清,思路才能清晰  视频讲解: 动态规划来决定最佳时机,这次有冷冻期!| LeetCode:309.买卖股票的最佳时机含冷冻期_哔哩哔哩_bilibili 代码随想录 相对122.买卖股票的最佳时机II ,本题只需要在计算卖出操

    2024年01月18日
    浏览(55)
  • 算法训练day41|动态规划 part03(LeetCode343. 整数拆分、96.不同的二叉搜索树)

    题目链接🔥🔥 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 说明: 你可以假设 n 不小于 2 且不大于

    2024年02月10日
    浏览(42)
  • Leetcoder Day39| 动态规划part06 完全背包问题

    有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。 每件物品都有无限个(也就是可以放入背包多次) ,求解将哪些物品装入背包里物品价值总和最大。 示例: 背包最大重量为4。 物品为: 重量 价值 物品0 1 15 物品1 3 20 物品2 4 30 每

    2024年03月25日
    浏览(39)
  • 算法训练day37|贪心算法 part06(LeetCode738.单调递增的数字)

    题目链接🔥🔥 给定一个非负整数 N,找出小于或等于 N 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。 (当且仅当每个相邻位数上的数字 x 和 y 满足 x = y 时,我们称这个整数是单调递增的。) 示例 1: 输入: N = 10 输出: 9 示例 2: 输入: N = 1234 输出:

    2024年02月09日
    浏览(35)
  • 算法 DAY44 动态规划6 完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ

    有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题唯一不同的地方就是,每种物品有无限件。 动规五步曲来分

    2024年02月01日
    浏览(53)
  • 代码随想录Day41:动态规划Part3

    讲解前: 毫无头绪 讲解后: 这道题的动态思路一开始很不容易想出来,虽然dp数组的定义如果知道是动态规划的话估摸着可以想出来那就是很straight forward dp定义:一维数组dp[i], i 代表整数的值,dp[i] 代表将整数 i 拆分的话可以获得的最大乘积 然后呢就是定义递归推导式了,

    2024年04月27日
    浏览(43)
  • 力扣算法刷题Day44|动态规划:完全背包问题 零钱兑换II 组合总和Ⅳ

    力扣题目:#518.零钱兑换II(完全背包组合问题) 刷题时长:7min 解题方法:动态规划(完全背包) 复杂度分析 时间复杂度: O(mn),其中 m 是amount,n 是 coins 的长度 空间复杂度: O(m) 问题总结 对递推公式的理解 本题收获 题意转换:纯完全背包是凑成背包最大价值是多少,而本

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

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

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

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

    2024年04月14日
    浏览(56)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包