甲骨文面试题【动态规划】力扣377.组合总和IV

给你一个由 不同 整数组成的数组 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

在这里插入图片描述


看逻辑图把逻辑理清楚,弄明白dp[i]储存的是什么,然后为什么要减去num的目的是什么。(拿图请标明出处)
在这里插入图片描述

在这里插入图片描述

代码

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target + 1);dp[0] = 1;for(int i=1;i<=target;i++){for(int num : nums){if(num <= i && dp[i-num] < INT_MAX - dp[i]){dp[i] += dp[i - num];}}}return dp[target];}
};

注意dp[i-num] < INT_MAX - dp[i]不可以写成
dp[i-num] + dp[i] < INT_MAX ,因为先进行求和再检查是不安全的,如果求和大于INT_MAX,会发生溢出,导致结果变为负数或者一个不可预测的值,可能会导致检查通过。

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

QTableView仿Excel表头排序和筛选

一.效果 Excel的排序和筛选弹窗如下所示 功能非常强大。不仅支持内容排序和筛选,还支持颜色的排序和筛选,而且还支持设置多种过滤条件。本文只仿最常用的内容排序和内容单过滤条件的筛选,效果如下所示。 从效果图中可以看出,表头Section中的按钮有下列六种状态 enum Butt…

Redis 教程:从入门到入坑

目录 1. Redis 安装与启动1.1. 安装 Redis1.1.1. 在Linux上安装1.1.2. 在Windows上安装 1.2. 启动 Redis1.2.1. 在Linux上启动1.2.2. 在Windows上启动 1.3. 连接Redis1.3.1. 连接本地Redis1.3.2. 连接远程Redis1.3.2.1. 服务器开放端口1.3.2.2. 关闭防火墙1.3.2.3. 修改配置文件…

GESP CCF C++ 三级认证真题 2024年6月

第 1 题 小杨父母带他到某培训机构给他报名参加CCF组织的GESP认证考试的第1级&#xff0c;那他可以选择的认证语言有&#xff08;&#xff09;种。 A. 1 B. 2 C. 3 D. 4 第 2 题 下面流程图在yr输入2024时&#xff0c;可以判定yr代表闰年&#xff0c;并输出 2月是29天 &#x…

【整体介绍】HTML和JS编写多用户VR应用程序的框架

一、Networked-Aframe是什么&#xff1f; 简称NAF&#xff0c;底层基于Mozilla的AFrame框架&#xff0c;用HTML和JS编写多用户VR应用程序的框架。 二、特性 支持 WebRTC 和/或 WebSocket 连接。 语音聊天。音频流让您的用户在应用程序内交谈&#xff08;仅限 WebRTC&#xff…

AV1技术学习: Compound Prediction

一、双向 Compound Prediction AV1支持两个参考帧的预测通过多种复合模式线性组合。复合预测公式为 其中&#xff0c;权重m(x, y) is scaled by 64 以进行整数计算&#xff0c;R1(x, y)和R2(x, y)表示两个参考块中位于(x, y)的像素。P(x, y)将按比例缩小 1/64 以形成最终的预测…

Android安卓使用MQTT(JAVA)

一、app目录下添加 implementation org.eclipse.paho:org.eclipse.paho.client.mqttv3:1.1.0 1) 点击Sync Now更新依赖 2) AndroidManifest.xml文件添加网络权限 <uses-permission android:name"android.permission.INTERNET"/> 二、 使用 1) 创建MqttConn…

使用 ABBYY FineReader PDF 15 在创建或转换 PDF 时自动生成书签

使用 ABBYY 为 PDF 文件添加书签&#xff0c;可以帮助快速定位文档中的主要内容&#xff0c;也能更方便的梳理出一份文档大纲。 有很多 PDF 文件在创建时并没有编辑书签&#xff0c;这里介绍使用 ABBYY FineReader PDF 15&#xff08;Win 系统&#xff09;在 PDF 中自动添加书…

postMessageXss续2

原文地址如下:https://research.securitum.com/art-of-bug-bounty-a-way-from-js-file-analysis-to-xss/ 在19年我写了一篇文章&#xff0c;是基于postMessageXss漏洞的入门教学:https://www.cnblogs.com/piaomiaohongchen/p/14727871.html 这几天浏览mXss技术的时候&#xff…

第三周周三总结

1.给你一个 32 位的有符号整数 x &#xff0c;返回将 x 中的数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] &#xff0c;就返回 0。 假设环境不允许存储 64 位整数&#xff08;有符号或无符号&#xff09;。 示例 1&#xff1a; 输…

RuoYi-后端管理项目入门篇1

目录 前提准备 下载若依前后端 Gitee 地址 准备环境 后端数据库导入 1 克隆完成 若依后端管理后端 Gitte 地址 :若依/RuoYi-Vue 2.1 创建Data Source数据源 2.2 填写好对应的数据库User 和 Password 点击Apply 2.3 新建一个Schema 2.4 填写对应数据库名称 这边演示写的…

【I²C协议】STC89C51单片机IIC通信(代码+原理)

STC89C51单片机IIC通信 什么是IC协议特点构成 通信协议开始信号、结束信号、应答信号数据传输 代码示例 什么是IC协议 IIC,即IC&#xff0c;全称 Inter-Integrated Circuit&#xff0c;字面上的意思是集成电路之间&#xff0c;它其实是IC Bus简称&#xff0c;所以中文应该叫 集…

【Codeforces】Round 957 (Div. 3)_B. Angry Monk

作者&#xff1a;指针不指南吗 专栏&#xff1a;算法刷题 &#x1f43e;或许会很慢&#xff0c;但是不可以停下来&#x1f43e; 文章目录 题目题解try1代码正确题解贪心策略的解释为什么不是直接合并 总结 题目 题目链接 题解 try1代码 我的思路&#xff1a;单纯模拟 循环&a…

【字幕】字幕特效入门

前言 最近两周调研了一下字幕特效的底层程序逻辑&#xff0c;因为工作内容的原因&#xff0c;就分享几个自己找的链接具体细节就不分享了&#xff0c;CSDN也是我的个人笔记&#xff0c;只记录一些简单的内容用于后续自己方便查询&#xff0c;顺便帮助一下正在苦苦查阅资料入门…

基于STC89C51单片机的烟雾报警器设计(煤气火灾检测报警)(含文档、源码与proteus仿真,以及系统详细介绍)

本篇文章论述的是基于STC89C51单片机的烟雾报警器设计的详情介绍&#xff0c;如果对您有帮助的话&#xff0c;还请关注一下哦&#xff0c;如果有资源方面的需要可以联系我。 目录 摘要 原理图 实物图 仿真图 元件清单 代码 系统论文 资源下载 摘要 随着现代家庭用火、…

【高中数学/指数函数、幂函数】寻找曲线y=2^x与y=x^2的三个交汇点

【问题】 找到曲线y2^x与yx^2的三个交汇点。 【难点】 指数和二次函数摆在一起没法求解。 【解答】 y2^x与yx^2的交汇点&#xff0c;即曲线y2^x-x^2的零点&#xff0c;用Canvas作图就能清晰看到三个零点的存在&#xff0c;如图。 【图一】 其中&#xff0c;2&#xff0c;…

自制连点器

B站使用教程&#xff1a;https://www.bilibili.com/video/BV1SR85e4EKw/?vd_source47eba1800d831e86d4778a128740fe73 下载链接&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1Spv_yVPFB3zoS__VL-nhaQ?pwdyxo1 提取码&#xff1a;yxo1

排序算法(4)之快速排序(1)

个人主页&#xff1a;C忠实粉丝 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 C忠实粉丝 原创 排序算法(4)之快速排序(1) 收录于专栏【数据结构初阶】 本专栏旨在分享学习数据结构学习的一点学习笔记&#xff0c;欢迎大家在评论区交流讨论&#x1f48c; 目…

langchain循序渐进之langchain 安装及使用

pip安装langchain pip install langchain安装langsmith(可选) langsmith官方提示是用来观察大模型复杂调用情况&#xff0c;可选项。 [LangSmith]点击注册然后把秘钥填进去就行&#xff0c;这里我略过了 export LANGCHAIN_TRACING_V2"true" export LANGCHAIN_A…

【C++】模版初阶以及STL的简介

个人主页~ 模版及STL 一、模版初阶1、泛型编程2、函数模版&#xff08;1&#xff09;概念&#xff08;2&#xff09;函数模版格式&#xff08;3&#xff09;函数模版的原理&#xff08;4&#xff09;函数模版的实例化①显式实例化②隐式实例化 &#xff08;5&#xff09;模版参…

精益六西格玛项目赋能,石油机械龙头企业质量效率双提升!

​国内某石油机械制造龙头&#xff0c;迎接挑战&#xff0c;迈向卓越&#xff0c;携手张驰咨询&#xff0c;启动精益六西格玛项目&#xff0c;开启管理革新新篇章。 在国家政策调整和市场竞争日益激烈的背景下&#xff0c;作为国内石油机械产品制造领域的龙头企业&#xff0c;…