动态规划 -背包问题-详解
问题
注:大佬对此类问题的解法:动态规划背包问题总结
给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1:
输入:nums = [1,2,3], target = 4
输出:7
解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意,顺序不同的序列被视作不同的组合。
示例 2:
输入:nums = [9], target = 3
输出:0
提示:
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000
程序
#include <stdio.h>// 定义一个函数来计算总和为目标整数的元素组合的个数
int combinationSum4(int* nums, int numsSize, int target) {// 创建一个动态规划数组 dp,长度为 target + 1int dp[target + 1];// 初始化 dp 数组,将所有元素初始化为0for (int i = 0; i <= target; i++) {dp[i] = 0;}// 初始状态:总和为0时,只有一种组合方式,即什么都不选dp[0] = 1;// 开始填充 dp 数组for (int i = 1; i <= target; i++) {for (int j = 0; j < numsSize; j++) {// 如果当前的目标总和减去数组元素可达if (i - nums[j] >= 0) {// 则将 dp[i] 增加 dp[i - nums[j]],表示加上当前元素后的组合数dp[i] += dp[i - nums[j]];}}}// 返回 dp 数组中最终目标总和的组合数return dp[target];
}int main() {int nums[] = {1, 2, 3};int target = 4;int numsSize = sizeof(nums) / sizeof(nums[0]);// 调用 combinationSum4 函数,计算组合数int result = combinationSum4(nums, numsSize, target);// 打印结果printf("输出:%d\n", result);return 0;
}
解释
在动态规划中,dp[i - nums[j]] 表示以目标值 i 减去数组中的某个元素 nums[j] 后的状态。这通常用于动态规划问题中,特别是在处理组合问题时,来记录前一步的状态。
在上述程序中,dp[i] 表示总和为 i 的组合数。当计算 dp[i] 时,我们遍历数组 nums 中的元素,对于每个元素 nums[j],我们考虑将其加入总和为 i 的组合中。为了计算 dp[i],我们需要考虑两种情况:
- 如果 i 大于等于 nums[j],那么我们可以将 nums[j] 加入到总和为 i 的组合中。此时,我们需要考虑的是将 nums[j] 加入后,剩余的总和为 i - nums[j] 的组合数,这就是 dp[i - nums[j]]。
- 如果 i 小于 nums[j],则 nums[j] 不能被加入到总和为 i 的组合中,因为它会导致总和超过
i。因此,在这种情况下,dp[i - nums[j]] 为0。
所以,dp[i - nums[j]] 表示以目标值 i 减去数组中的某个元素 nums[j] 后的状态,即剩余的部分。通过考虑所有可能的 nums[j],我们可以累加所有这些情况,以计算总和为 i 的组合数 dp[i]。这就是动态规划的思想:将较大问题分解成较小问题,并使用较小问题的解来构建较大问题的解。
假设数组 nums 为 [1, 2, 3],目标值 target 为 4。
初始时,dp 数组如下:
dp[0] = 1
dp[1] = 0
dp[2] = 0
dp[3] = 0
dp[4] = 0
开始计算 dp[1]:
- i 等于 1,nums[j] 等于 1,因此 i >= nums[j]。
- 我们考虑将 1 加入到总和为 1 的组合中,剩余的总和是 1 - 1 = 0。
- 此时,dp[0] 为1,因为只有一种组合方式,即什么都不选。
- 所以,dp[1] = dp[1 - 1] = dp[0] = 1。
继续计算 dp[2] 和 dp[3]: - dp[2] 的计算和 dp[1] 类似,因为我们可以将 2 加入到总和为 2 的组合中,dp[2] = dp[2 - 2] = dp[0] = 1。
- dp[3] 的计算也类似,因为我们可以将 3 加入到总和为 3 的组合中,dp[3] = dp[3 - 3] = dp[0] = 1。
最后,计算 dp[4]: - 对于 dp[4],我们可以考虑将 1 加入到总和为 4 的组合中,这就是 dp[4 - 1] = dp[3] = 1。
- 我们还可以考虑将 2 加入到总和为 4 的组合中,这就是 dp[4 - 2] = dp[2] = 1。
- 同样,我们可以考虑将 3 加入到总和为 4 的组合中,这就是 dp[4 - 3] = dp[1] = 1。
- 然后,将这些情况的组合数累加起来,即 dp[4] = 1 + 1 + 1 = 3。
最终,dp[4] 的值为 3,表示总和为 4 的组合数为 3 种,即 [1, 1, 1, 1]、[1, 1, 2] 和 [2, 2]。
相关文章:
动态规划 -背包问题-详解
问题 注:大佬对此类问题的解法:动态规划背包问题总结 给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 示例 1ÿ…...
Bootstrap-- 媒体特性
最大、最小宽度例子: 横屏与竖屏例子: 宽度比与像素比例子:...
c# 用非递归的写法实现递归
最近写代码碰到了一个bug,就是递归次数太多爆堆栈了,然后就写了一个递归工具来解决这个问题。 using System; using System.Collections.Generic;/// <summary> /// 递归工具 /// </summary> public static class RecursionTool {//递归方式…...
nginx之location的优先级和nginx的重定向
一、nginx之location的优先级和匹配方式(重点) (一)nginx的正则表达式 nginx的正则表达式 符号 含义 ^ 字符串的起始位置(以什么开头) $ 字符串的结束位置(以什么结尾) * 匹…...
【计算机网络】——前言计算机网络发展的历程概述
主页点击直达:个人主页 我的小仓库:代码仓库 C语言偷着笑:C语言专栏 数据结构挨打小记:初阶数据结构专栏 Linux被操作记:Linux专栏 LeetCode刷题掉发记:LeetCode刷题 算法:算法专栏 C头…...
eventfd
1. #include <sys/eventfd.h> int eventfd(unsigned int initval, int flags); //创建eventfd 参数含义: initval:创建eventfd时它所对应的64位计数器的初始值; flags:eventfd文件描述符的标志,可由三种选项组…...
BES耳机空间音频技术实现
BES耳机空间音频技术实现 是否需要申请加入数字音频系统研究开发交流答疑群(课题组)?加我微信hezkz17, 本群提供音频技术答疑服务 音响和耳机在空间音频技术上实现方式是不同的 虚拟现实可谓是空间音频技术最具代表性的应 用领域。虽然虚拟现实的起源可以追溯到1 9 6 8年, …...
day27--AJAX(bootstrap之modal,toast;接口文档的一些用法;AJAX原理)
目录 Bootstrap之Modal: 显示和隐藏方法 通过自定义属性: 使用JS来控制弹框: Bootstrap之Toast: 接口文档一些用法: 删除图书: 图片上传: 图片上传步骤: 修改头像…...
【ArcGIS Pro二次开发】(70):杂七杂八的记录
本文用于记录一些使用频率较高但归类繁杂,非系统性的一些代码。 主要方便自己使用和查阅,随时更新。 1、从GDB数据库中打开【FeatureDataset\FeatureClass\Table】 using Geodatabase gdb new Geodatabase(new FileGeodatabaseConnectionPath(new Uri…...
竞赛选题 深度学习 机器视觉 人脸识别系统 - opencv python
文章目录 0 前言1 机器学习-人脸识别过程人脸检测人脸对其人脸特征向量化人脸识别 2 深度学习-人脸识别过程人脸检测人脸识别Metric Larning 3 最后 0 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 深度学习 机器视觉 人脸识别系统 该项目…...
【工具】SSH端口转发管理器,专门管理SSH Port Forwarding
转载请注明出处:小锋学长生活大爆炸[xfxuezhang.cn] 开源代码看这里:http://xfxuezhang.cn/index.php/archives/1151/ 背景介绍 有时候需要用到ssh的端口转发功能。目前来说,要么是cmd里手敲指令,但每次敲也太麻烦了;或…...
opencv-phase 函数
计算梯度强度和方向 梯度的方向与边缘的方向总是垂直的。图像中的边缘可以指向各个方向,通常会取水平(左、右)、垂直(上、下)、对角线(左上、右上、左下、右下)等八个不同的方向计算梯度。 角度…...
44.ES
一、ES。 (1)es概念。 (1.1)什么是es。 (1.2)es的发展。 es是基于lucene写的。 (1.3)总结。 es是基于lucene写的。 (2)倒排索引。 (3…...
分权分域有啥内容?
目前的系统有什么问题? 现在我们的系统越来越庞大,可是每一个人进来的查看到的内容完全一样,没有办法灵活的根据不同用户展示不同的数据 例如我们有一个系统,期望不同权限的用户可以看到不同类型的页面,同一个页面不…...
6.Docker搭建RabbitMQ
1、端口开放 如果在云服务上部署需在安全组开通一下端口:15672、5672、25672、61613、1883。 15672(UI页面通信口)、5672(client端通信口)、25672(server间内部通信口)、61613(stomp 消息传输)、1883(MQTT消息队列遥测传输)。 2、安装镜像 docker pull rabbitmq 3、…...
用 docker 创建 jmeter 容器, 实现性能测试,该如何下手?
用 docker 创建 jmeter 容器, 实现性能测试 我们都知道,jmeter可以做接口测试,也可以用于性能测试,现在企业中性能测试也大多使用jmeter。docker是最近这些年流行起来的容器部署工具,可以创建一个容器,然后把项目放到…...
4年软件测试,突破不了20K,太卷了。。。
先说一个插曲:上个月我有同学在深圳被裁员了,和我一样都是软件测试,不过他是平安外包,所以整个组都撤了,他工资和我差不多都是14K。 现在IT互联网已经比较寒冬,特别是软件测试,裁员先裁测试&am…...
机器人控制算法——两轮差速驱动运动模型
1.Introduction 本文主要介绍针对于两轮差速模型的逆运动学数学推导。因为在机器人控制领域,决策规划控制层给执行器输出的控制指令v(车辆前进速度)和w(角速度),因此,我们比较关心,当底层两个驱动电机接收到此信息,如何…...
Queue简介
概念: 队列(Queue)是一种常见的线性数据结构,在Java中用于存储和操作元素序列。它基于先进先出(First-In-First-Out, FIFO)原则,即最早入队的元素首先出队。只能在队尾添加元素,在队…...
被面试官问到分布式ID,别再傻乎乎只会答雪花算法了...
文章目录 1. 分布式ID2. 数据库主键自增3. 数据库号段模式4. Redis自增5. UUID6. Snowflake (雪花算法)7. Leaf (美团分布式ID生成系统)7.1 Leaf-segment 号段方案7.1.2 双buffer优化 7.2 Leaf-snowflake方案7.3 Leaf-snowflake Demo 1. 分布式ID 在分布式系统中,通…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...
抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
