代码随想录算法训练营三刷day44 | 动态规划之 完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ

本文主要是介绍代码随想录算法训练营三刷day44 | 动态规划之 完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

三刷day44

      • 完全背包基础知识
        • 问题描述
        • 举个栗子
      • 518. 零钱兑换 II
        • 1.确定dp数组以及下标的含义
        • 2.确定递推公式
        • 3.dp数组如何初始化
        • 4.确定遍历顺序
        • 5.举例推导dp数组
      • 377. 组合总和 Ⅳ
        • 1.确定dp数组以及下标的含义
        • 2.确定递推公式
        • 3.dp数组如何初始化
        • 4.确定遍历顺序
        • 5.举例来推导dp数组

完全背包基础知识

问题描述

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

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

举个栗子

背包最大重量为4。

重量价值
物品0115
物品1320
物品2430

完全背包的物品是可以添加多次的,所以要从小到大去遍历
在这里插入图片描述

// 先遍历物品,在遍历背包
void test_CompletePack() {vector<int> weight = {1, 3, 4};vector<int> value = {15, 20, 30};int bagWeight = 4;vector<int> dp(bagWeight + 1, 0);for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[bagWeight] << endl;
}
int main() {test_CompletePack();
}

518. 零钱兑换 II

题目链接
解题思路: 纯完全背包是凑成背包最大价值是多少,而本题是要求凑成总金额的物品组合个数!是一个组合问题。组合不强调元素之间的顺序,排列强调元素之间的顺序。

动规五步曲:

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

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

2.确定递推公式

dp[j] 就是所有的dp[j - coins[i]](考虑coins[i]的情况)相加。

所以递推公式:dp[j] += dp[j - coins[i]];

这个递推公式01背包题目的时候在这篇494. 目标和
(opens new window)中出现过,求装满背包有几种方法,公式都是:dp[j] += dp[j - nums[i]];

3.dp数组如何初始化

首先dp[0]一定要为1,dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话,后面所有推导出来的值都是0了。

dp[0]=1还说明了一种情况:如果正好选了coins[i]后,也就是j-coins[i] == 0的情况表示这个硬币刚好能选,此时dp[0]为1表示只选coins[i]存在这样的一种选法。

4.确定遍历顺序

本题中我们是外层for循环遍历物品(钱币),内层for遍历背包(金钱总额),还是外层for遍历背包(金钱总额),内层for循环遍历物品(钱币)呢?在上面的讲解中完全背包的两个for循环的先后顺序都是可以的。

但本题就不行了!

因为纯完全背包求得装满背包的最大价值是多少,和凑成总和的元素有没有顺序没关系,即:有顺序也行,没有顺序也行!

而本题要求凑成总和的组合数,元素之间明确要求没有顺序。

所以纯完全背包是能凑成总和就行,不用管怎么凑的。

本题是求凑出来的方案个数,且每个方案个数是为组合数。

那么本题,两个for循环的先后顺序可就有说法了。

我们先来看 外层for循环遍历物品(钱币),内层for遍历背包(金钱总额)的情况。
代码如下:

for (int i = 0; i < coins.size(); i++) { // 遍历物品for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量dp[j] += dp[j - coins[i]];}
}

假设:coins[0] = 1,coins[1] = 5

那么就是先把1加入计算,然后再把5加入计算,得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

所以这种遍历顺序中dp[j]里计算的是组合数!

如果把两个for交换顺序,代码如下:

for (int j = 0; j <= amount; j++) { // 遍历背包容量for (int i = 0; i < coins.size(); i++) { // 遍历物品if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];}
}

背包容量的每一个值,都是经过 1 和 5 的计算,包含了{1, 5}{5, 1}两种情况。

此时dp[j]里算出来的就是排列数!

5.举例推导dp数组

输入: amount = 5, coins = [1, 2, 5] ,dp状态图如下:
在这里插入图片描述最后红色框dp[amount]为最终结果。
C++代码如下:

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1, 0);dp[0] = 1;for (int i = 0; i < coins.size(); i++) { // 遍历物品for (int j = coins[i]; j <= amount; j++) { // 遍历背包dp[j] += dp[j - coins[i]];}}return dp[amount];}
};

377. 组合总和 Ⅳ

题目链接
解题思路:本题题目描述说是求组合,但又说是可以元素相同顺序不同的组合算两个组合,其实就是求排列

动规五部曲分析如下:

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

dp[i]: 凑成目标正整数为i的排列个数为dp[i]

2.确定递推公式

dp[i](考虑nums[j])可以由 dp[i - nums[j]](不考虑nums[j]) 推导出来。

因为只要得到nums[j],排列个数dp[i - nums[j]],就是dp[i]的一部分。

求装满背包有几种方法,递推公式一般都是dp[i] += dp[i - nums[j]];

本题也一样。

3.dp数组如何初始化

因为递推公式dp[i] += dp[i - nums[j]]的缘故,dp[0]要初始化为1,这样递归其他dp[i]的时候才会有数值基础。

至于dp[0] = 1 有没有意义呢?

其实没有意义,所以我也不去强行解释它的意义了,因为题目中也说了:给定目标值是正整数! 所以dp[0] = 1是没有意义的,仅仅是为了推导递推公式。

至于非0下标的dp[i]应该初始为多少呢?

初始化为0,这样才不会影响dp[i]累加所有的dp[i - nums[j]]

4.确定遍历顺序

个数可以不限使用,说明这是一个完全背包。

得到的集合是排列,说明需要考虑元素之间的顺序。

本题要求的是排列,那么这个for循环嵌套的顺序可以有说法了。

如果求组合数就是外层for循环遍历物品,内层for遍历背包。

如果求排列数就是外层for遍历背包,内层for循环遍历物品。

如果把遍历nums(物品)放在外循环,遍历target的作为内循环的话,
举个栗子:
计算dp[4]的时候,结果集只有 {1,3} 这样的集合,不会有{3,1}这样的集合,因为nums遍历放在外层,3只能出现在1后面!

所以本题遍历顺序最终遍历顺序:target(背包)放在外循环,将nums(物品)放在内循环,内循环从前到后遍历。

5.举例来推导dp数组

我们再来用示例中的例子推导一下:
输入:nums =[1,2,3] , target = 4
在这里插入图片描述
C++代码如下:

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target + 1, 0);dp[0] = 1;for (int i = 0; i <= target; i++) { // 遍历背包for (int j = 0; j < nums.size(); j++) { // 遍历物品if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {dp[i] += dp[i - nums[j]];}}}return dp[target];}
};

这篇关于代码随想录算法训练营三刷day44 | 动态规划之 完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL