代码随想录算法训练营 动态规划part06

一、完全背包

卡哥的总结,还挺全代码随想录 (programmercarl.com)

二、零钱兑换 II 

518. 零钱兑换 II - 力扣(LeetCode)

被选物品之间不需要满足特定关系,只需要选择物品,以达到「全局最优」或者「特定状态」即可。

同时硬币相当于我们的物品,每种硬币可以选择「无限次」,很自然的想到「完全背包」。

这时候可以将「完全背包」的状态定义搬过来进行“微调”:

定义 f[i][j]为考虑前 iii 件物品,凑成总和为 jjj 的方案数量。

为了方便初始化,我们一般让 f[0][x] 代表不考虑任何物品的情况。

因此我们有显而易见的初始化条件:f[0][0]=1,其余 f[0][x]=0。

代表当没有任何硬币的时候,存在凑成总和为 0 的方案数量为 1;凑成其他总和的方案不存在。

当「状态定义」与「基本初始化」有了之后,我们不失一般性的考虑 f[i][j] 该如何转移。

对于第 i 个硬币我们有两种决策方案:

不使用该硬币:
f[i−1][j]

使用该硬币:由于每个硬币可以被选择多次(容量允许的情况下),因此方案数量应当是选择「任意个」该硬币的方案总和:

class Solution {public int change(int cnt, int[] cs) {int n = cs.length;int[][] f = new int[n + 1][cnt + 1];f[0][0] = 1;for (int i = 1; i <= n; i++) {int val = cs[i - 1];for (int j = 0; j <= cnt; j++) {f[i][j] = f[i - 1][j];for (int k = 1; k * val <= j; k++) {f[i][j] += f[i - 1][j - k * val];  }}}return f[n][cnt];}
}

三、组合总和 Ⅳ  

377. 组合总和 Ⅳ - 力扣(LeetCode)

emmmmm看官方题解吧377. 组合总和 Ⅳ - 力扣(LeetCode)

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

eclipse如何引入lombok插件

1. 下载插件 Downloadhttps://projectlombok.org/downloadlombok插件是一个jar包&#xff0c;如下图&#xff1a; 2. 安装插件 双击运行下载的jar包&#xff0c;点击如下按钮&#xff1a; 在弹窗内选择eclipse的启动程序eclipse.exe&#xff0c;注意&#xff01;&#xff01;…

基于springboot+vue的车辆管理系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战 主要内容&#xff1a;毕业设计(Javaweb项目|小程序等)、简历模板、学习资料、面试题库、技术咨询 文末联系获取 项目介绍…

4、SpringBoot_Mybatis、Druid、Juint整合

五、SSM整合 1.整合Mybatis 1.1springmvc 整合回顾 导入坐标 <dependency><groupId>org.springframework</groupId><artifactId>spring-jdbc</artifactId><version>5.2.17.RELEASE</version></dependency><dependency>…

XAPI项目架构:应对第三方签名认证的设计与调整

《XAPI项目》&#xff1a;GitHub仓库&#xff08;勿打&#x1f6ab;小破站一个&#xff09; 该项目是基于鱼皮的《API开发平台》项目的需求和架构设计上进行Golang版本开发的。 这篇文章&#xff0c;主要内容是记录在《XAPI项目》的原架构上&#xff0c;为了应对第三方签名认证…

js中的数据结构:栈,队列,链表,字典哈希表,树

栈&#xff1a;先进后出 队列&#xff1a;先进先出 链表&#xff1a; 单链表&#xff1a; 双链表&#xff1a; 环形链表&#xff1a;最后一个数据的next指针不是指向null&#xff0c;指向的是任意之间的一个数据&#xff0c;形成一个环 数组和链表的区别&#xff1a; 字典和哈…

Docker Desktop 界面功能介绍,添加国内镜像源

目录 镜像源修改设置 其他偏好设置 镜像源修改设置 默认情况下&#xff0c;Docker Desktop会从Docker Hub下载镜像&#xff0c;但在国内由于网络的原因&#xff0c;下载速度可能较慢&#xff0c;配置国内镜像源可以提速镜像下载。在Docker Desktop中配置镜像源非常简单&…

LLM各层参数详细分析(以LLaMA为例)

网上大多分析LLM参数的文章都比较粗粒度&#xff0c;对于LLM的精确部署不太友好&#xff0c;在这里记录一下分析LLM参数的过程。 首先看QKV。先上transformer原文 也就是说&#xff0c;当h&#xff08;heads&#xff09; 1时&#xff0c;在默认情况下&#xff0c; W i Q W_i^…

2023/09/20 day4 qt

做一个动态指针钟表 头文件 #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QPainter> //绘制事件类 #include <QPaintEvent> //画家类 #include <QTime> #include <QTimer> #include <QTimerEvent> QT_BEGIN…

用于设计 CNN 的 7 种不同卷积

一 说明 最近对CNN架构的研究包括许多不同的卷积变体&#xff0c;这让我在阅读这些论文时感到困惑。我认为通过一些更流行的卷积变体的精确定义&#xff0c;效果和用例&#xff08;在计算机视觉和深度学习中&#xff09;是值得的。这些变体旨在保存参数计数、增强推理并利用目标…

rtsp转webrtc的其他几个项目

1&#xff09; mpromonet/webrtc-streamer &#xff08;c开发&#xff09; 把rtsp转webrtc&#xff0c; 通过 load urls from JSON config file ./webrtc-streamer -C config.json 通过exe文件和docker项目实际测试可以显示&#xff0c;但不太稳定加载慢,有时候出错后很难…

7.15 SpringBoot项目实战 【学生入驻】(上):从API接口定义 到 Mybatis查询 串讲

文章目录 前言一、service层 和 dal层方式一、Example方式方式二、Mybatis XML方式方式三、Mybatis 注解方式 二、web层 StudentController最后 前言 接下来我们实战【学生入驻】&#xff0c;对于C端学生端&#xff0c;一切交互开始于知道 当前学生是否入驻、是否有借阅资格&a…

LeetCode 753. 破解保险箱【欧拉回路,DFS】困难

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…

java字符串压缩和字符串解压

java字符串压缩和字符串解压 运行效果 java工具类 CompressUtil.java import com.alibaba.fastjson.JSON; import com.alibaba.fastjson.serializer.SerializerFeature; import org.apache.commons.codec.binary.Base64;import java.io.BufferedReader; import java.io.Byte…

el-form自定义规则后表单验证validate不生效的问题

1.首先放出结论&#xff0c;自定义验证规则必须降所有的可能全部都return callback出去&#xff0c;不然不会走validate 错误示范 // template <el-formref"ruleFormRef":model"ruleForm":rules"rules"label-width"120px"class&qu…

力扣:105. 从前序与中序遍历序列构造二叉树(Python3)

题目&#xff1a; 给定两个整数数组 preorder 和 inorder &#xff0c;其中 preorder 是二叉树的先序遍历&#xff0c; inorder 是同一棵树的中序遍历&#xff0c;请构造二叉树并返回其根节点。 来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 链接&#xff1a;力扣&am…

Visio——绘制倾斜线段

一、形状 -> 图表和数学图形 -> 多行 二、放置多行线&#xff0c;可以发现存在两个折点 三、选择多行线&#xff0c;右键选择删除点&#xff0c;即可得到倾斜线段

C进阶-数据的存储

数据类型介绍 内置类型&#xff1a; //数据类型中的内置类型 // char //字符数据类型 // short //短整型 // int //整型 // long //长整型 // long long //更长的整型 // float //单精度浮点数 // double //双精度浮点数 //数据类型中的内置类型 单位是字节 // char //字…

PyCharm 手动下载插件

插件模块一直加载失败&#xff0c;报错信息&#xff1a; Marketplace plugins are not loaded. Check the internet connection and refresh. 尝试了以下方法&#xff0c;均告失败&#xff1a; pip 换源Manage Plugin Repositories...HTTP 代理设置...关闭三个防火墙 最后选…

《动手学深度学习 Pytorch版》 7.4 含并行连接的网络(GoogLeNet)

import torch from torch import nn from torch.nn import functional as F from d2l import torch as d2l7.4.1 Inception块 GoogLNet 中的基本卷积块叫做 Inception 块&#xff08;大概率得名于盗梦空间&#xff09;&#xff0c;由 4 条并行路径组成。 前 3 条路径使用窗口…

华为云云耀云服务器L实例评测|使用云耀云服务器L实例,自行搭建NextCloud

背景 本人是搞分布式存储的&#xff0c;一心想搭个网盘&#xff0c;发现L实例里面就有个网盘实例最低配置是2核4G&#xff0c;为了节省成本&#xff0c;选个【2核2G】的配置&#xff0c;一样可以搭起来。 简介 Nextcloud是一款开源免费的私有云存储网盘项目&#xff0c;可以让…