代码随想录算法训练营第四十六天 _ 动态规划_背包问题总结。

学习目标:

动态规划五部曲:
① 确定dp[i]的含义
② 求递推公式
③ dp数组如何初始化
④ 确定遍历顺序
⑤ 打印递归数组 ---- 调试
引用自代码随想录!

本文大多数内容引用自代码随想录

60天训练营打卡计划!

学习内容:

背包问题总结
上述内容引用自代码随想录

  • 使用动归五部曲分析题目,见过的题目就可以被轻松带走。最重要的就是dp[]数组的含义,递归函数即遍历的顺序。

1.背包递推公式

能否能装满背包(或者最多装多少):
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ,对应题目如下:

  • 动态规划:416.分割等和子集
  • 动态规划:1049.最后一块石头的重量 II
  • 动态规划:139.单词拆分

问装满背包有几种方法:dp[j] += dp[j - nums[i]] ,对应题目如下:

  • 动态规划:494.目标和
  • 动态规划:518. 零钱兑换 II
  • 动态规划:377.组合总和Ⅳ
  • 动态规划:70. 爬楼梯进阶版(完全背包)

问背包装满最大价值
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ,对应题目如下:

  • 动态规划:474.一和零

问装满背包所有物品的最小个数:dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ,对应题目如下:

  • 动态规划:322.零钱兑换
  • 动态规划:279.完全平方数

2.遍历顺序

01背包

二维dp数组01背包先遍历物品还是先遍历背包都是可以的,且第二层for循环是从小到大遍历。一维dp数组01背包只能先遍历物品再遍历背包容量,且第二层for循环是从大到小遍历。

完全背包

说完01背包,再看看完全背包。

一维dp数组实现,先遍历物品还是先遍历背包都是可以的,且第二层for循环是从小到大遍历。但是仅仅是纯完全背包的遍历顺序是这样的,题目稍有变化,两个for循环的先后顺序就不一样了。

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

相关题目如下:

求组合数:

  • 动态规划:518.零钱兑换II

求排列数:

  • 动态规划:377. 组合总和 Ⅳ
  • 动态规划:70. 爬楼梯进阶版(完全背包)

如果求最小数,那么两层for循环的先后顺序就无所谓了,相关题目如下:
求最小数:

  • 动态规划:322. 零钱兑换
  • 动态规划:279.完全平方数

对于背包问题,其实递推公式算是容易的,难是难在遍历顺序上,如果把遍历顺序搞透,才算是真正理解了。


学习时间:

  • 上午两个半小时,整理文档半小时。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/235518.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

银行插件导致的Outlook客户端无法连接服务器问题

问题现象 最近遇到好些同事出现outlook客户端无法连接服务器的情况,具体现象就是右下角一直显示【正在尝试连接…】或者【需要密码】,点击【需要密码】按钮,输密码的弹窗是一个完全空白的页面。 此时打开word,右上角那里去登录o…

Postman获取token

问题描述 登录接口中带有token参数,其他接口需要带上token才能正确访问,利用接口查询用户信息时手动在headers中更新token信息并不方便。 解决方案 在登录接口中设置一个名为“token”的环境变量,value为登录接口跑通之后responseBody中返回…

科技提升安全,基于YOLOv4开发构建商超扶梯场景下行人安全行为姿态检测识别系统

在商超等人流量较为密集的场景下经常会报道出现一些行人在扶梯上摔倒、受伤等问题,随着AI技术的快速发展与不断普及,越来越多的商超、地铁等场景开始加装专用的安全检测预警系统,核心工作原理即使AI模型与摄像头图像视频流的实时计算&#xf…

⭐Unity 搭建UDP客户端(01) 配合网络调试助手测试

1.接收来自服务器的消息 using System.Net; using System.Net.Sockets; using System.Text; using System.Threading; using UnityEngine;public class UDPManager:MonoBehaviour {public string recvStr; //服务器返回值public string UDPClientAddRess "192.168.2.39&q…

【算法系列篇】递归、搜索和回溯(二)

文章目录 前言1. 两两交换链表中的节点1.1 题目要求1.2 做题思路1.3 代码实现 2. Pow(X,N)2.1 题目要求2.2 做题思路2.3 代码实现 3. 计算布尔二叉树的值3.1 题目要求3.2 做题思路3.3 代码实现 4. 求根节点到叶结点数字之和4.1 题目要求4.2 做题思路4.3 代码实现 前言 前面为大…

Uniapp - 环境搭建 vscode开发

uni-app 基础 创建 uni-app 项目方式 uni-app 支持两种方式创建项目: 通过 HBuilderX 创建(需安装 HBuilderX 编辑器) 通过命令行创建(需安装 NodeJS 环境) HBuilderX 创建 uni-app 项目 创建步骤 1.下载安装 H…

Demystifying DeFi MEV Activities in Flashbots Bundle

目录 笔记后续的研究方向摘要引言贡献 Demystifying DeFi MEV Activities in Flashbots Bundle CCS 2023 笔记 本文介绍了对 Flashbots 捆绑包中的去中心化金融 (DeFi) 矿工可提取价值 (MEV) 活动的研究。作者开发了ActLifter&am…

SiC SBD/超结MOS在工业电源上的应用-REASUNOS瑞森半导体

一、前言 工业电源是指用于工业及相关领域中的电子设备与设施的电源系统,其重要性体现在为各类工业设备提供稳定的电力保障,维护设备正常运行,故需具有稳定可靠、高效节能、安全耐用等特点。 常见的工业电源类型包括:交流电源、…

优优聚:美团外卖,领跑外卖市场,打造全新就餐体验

随着互联网的快速发展,外卖行业逐渐崛起,成为了人们日常生活中不可或缺的一部分。作为中国最大的外卖平台之一,美团外卖凭借其卓越的服务和不断创新的精神,成为了市场的领导者。本文将详细分析美团外卖的发展现状以及其未来的发展…

使用cmake构建的工程的编译方法

1、克隆项目工程 2、进入到工程目录 3、执行 mkdir build && cd build 4、执行 cmake .. 5、执行 make 执行以上步骤即可完成对cmake编写的工程进行编译 ,后面只需执行你的编译结果即可 $ git clone 你想要克隆的代码路径 $ cd 代码文件夹 $ mkdir bu…

年入百万的知识付费网站如何搭建:如何以低成本实现高转化?

我有才知识付费平台 一、引言 随着知识经济的崛起,越来越多的知识提供者希望搭建自己的知识付费平台。然而,对于新手来说,如何以低成本、高效率地实现这一目标,同时满足自身需求并提高客户转化率,是一大挑战。本文将…

服务器GPU占用,kill -9 PID 用不了,解决办法

PID(progress ID 进程ID) 上图为占用情况,使用下面的指令都不管用 kill -9 PID kill -15 PID # 加入sudo 还是不行 # 等等网上的 chatgpt 提供的其他办法,一圈试了下来还是不管用最后解决办法 首先用下面的指令查看进程的树结构…

Linux基础命令-期末复习

目录 一、Linux文件和目录 1.mkdir创建目录 2.ls列出目录 3.pwd显示当前所在目录 4.cd切换目录 5.rmdir删除空的目录 6.rm删除文件或目录 7.touch创建文件 8.cp复制文件或目录 1.把文件从该目录复制到下一级目录中去 2.把文件从该目录复制到上一级目录中去 3.把文件…

第十四章 : Spring Boot 整合spring-session,使用redis共享

第十四章 : Spring Boot 整合spring-session,使用redis共享 前沿 本文重点讲述:spring boot工程中使用spring-session机制进行安全认证,并且通过redis存储session,满足集群部署、分布式系统的session共享。 基于SPringBoot 2.3.2…

大数据讲课笔记1.2 Linux用户操作

文章目录 零、学习目标一、导入新课二、新课讲解(一)用户账号管理1、用户与用户组文件2、用户账号管理工作 (二)用户操作1、切换用户(1)语法格式(2)切换到普通用户(3&…

HarmonyOS4.0从零开始的开发教程11给您的应用添加弹窗

HarmonyOS(十)给您的应用添加弹窗 概述 在我们日常使用应用的时候,可能会进行一些敏感的操作,比如删除联系人,这时候我们给应用添加弹窗来提示用户是否需要执行该操作,如下图所示: 弹窗是一种…

mysql面试题——日志

一:为什么需要REDO日志 缓冲池可以帮助我们消除CPU和磁盘之间的鸿沟,checkpoint机制可以保证数据的最终落盘,然而由于checkpoint 并不是每次变更的时候就触发 的,而是master线程隔一段时间去处理的。所以最坏的情况就是事务提交后…

GLAB | CCNA+HCIA=融合课-最新开课通知

敲重点! 12月17日 CCNAHCIA 周日开课啦! CCNA(Cisco Certified Network Associate)认证是Cisco售后工程师认证体系的入门认证,也是Cisco各项认证中级别最低的技术认证通过CCNA认证可证明你已掌握网络的基本知识,并能…

DL Homework 9

目录 1 知识总结 1.1 给网络增加短期的记忆能力 1.2 有外部输入的非线性自回归模型 1.3 循环神经网络 2.1 简单循环神经网络 2.1.1 循环神经网络的通用近似定理 2.1.2 图灵完备 3.1 序列到类别 3.2 同步的序列到序列模式 3.3 异步的序列到序列模式 2.Homework 1. 实现SRN &am…

JavaScript <关于逆向RSA非对称加密算法的案例(附原代码)>--案例(五)

前言: 趁热打铁,标记一下RSA的算法逆向...第二篇会有详解(本篇重在过程) 正文: 废话不说,直接分析步骤图: 到了这里,可以看到在登录的时候,需要验证码(本篇不教反验证码) 下面是正题--->逆他的pwd(密码) 总结: 问题:怎么确定一个密文数据是基于什么算法做出来的呢? 答:…