首页/新闻资讯/正文详情

DeepSeek LeetCode 518. 零钱兑换 II Java实现

发布时间:2026/11/5 7:54:51 来源:云帆数科 栏目:资讯中心
DeepSeek    LeetCode 518. 零钱兑换 II Java实现
LeetCode 518. 零钱兑换 II — Java 实现题目思路这是典型的完全背包问题· 硬币可以无限次使用· 求组合数不关心顺序· 与 322 题零钱兑换的区别322 求的是最少硬币数本题求的是方案总数核心代码一维 DP推荐classSolution{publicintchange(intamount,int[]coins){// dp[j] 表示凑成金额 j 的组合数int[]dpnewint[amount1];dp[0]1;// 凑成金额 0 只有一种方案什么都不选// 外层遍历硬币内层遍历金额正序 组合数for(intcoin:coins){for(intjcoin;jamount;j){dp[j]dp[j-coin];}}returndp[amount];}}为什么外层必须遍历硬币这是本题最关键的要点循环顺序 含义 结果外层硬币 / 内层金额正序 每种硬币逐个加入不会重复计算顺序 ✅ 组合数外层金额 / 内层硬币 每个金额位置枚举所有硬币考虑排列 ❌ 排列数示例coins [1, 2, 5], amount 5· 正确答案组合数 4· 5· 2 2 1· 2 1 1 1· 1 1 1 1 1· 如果顺序颠倒排列数会得到 9 种把 2111 和 1112 都算作不同方案二维 DP 版本辅助理解classSolution{publicintchange(intamount,int[]coins){intncoins.length;// dp[i][j] 用前 i 种硬币凑成金额 j 的组合数int[][]dpnewint[n1][amount1];// 初始化凑成金额 0 的方案数为 1空集for(inti0;in;i)dp[i][0]1;for(inti1;in;i){for(intj1;jamount;j){// 不使用第 i 种硬币dp[i][j]dp[i-1][j];// 使用第 i 种硬币可以重复使用所以是 dp[i][j - coin] 而不是 dp[i-1][j - coin]if(jcoins[i-1]){dp[i][j]dp[i][j-coins[i-1]];}}}returndp[n][amount];}}观察dp[i][j] 只依赖于 dp[i-1][j] 和 dp[i][j-coin]同一行的左侧因此可以压缩成一维——这就是推荐写法。复杂度分析· 时间复杂度O(n × amount)其中 n coins.length· 空间复杂度O(amount)边界情况情况 结果amount 0 1空方案coins []amount 0 0amount 无法凑出 0题目保证最终结果在 int 范围内不超过 2^31 - 1无需 long。

相关推荐

毕设/课设别再熬夜画图了!SpringBoot酒吧和夜店管理系统:功能结构图、流程图、数据流图、UML类图、时序图、用例图、三线表、用例表、开题报告,用捷码AI一键生成
毕设/课设别再熬夜画图了!SpringBoot酒吧和夜店管理系统:功能结构图、流程图、数据流图、UML类图、时序图、用例图、三线表、用例表、开题报告,用捷码AI一键生成

酒吧和夜店管理系统-综合设计成果/ ├── 00-交付清单/ manifest.json README ├── 01-系统图表/ 8 类系统图(E-R / 功能结构 / 数据流 / 架构 / 流程 / 类图 / 时序 / 用例) ├── 02-设计资料/ 数据库脚本 └── 03-交付成… · 2026/11/5 7:53:51

毕设/课设别再熬夜画图了!SpringBoot考务管理系统:功能结构图、流程图、数据流图、UML类图、时序图、用例图、三线表、用例表、开题报告,用捷码AI一键生成
毕设/课设别再熬夜画图了!SpringBoot考务管理系统:功能结构图、流程图、数据流图、UML类图、时序图、用例图、三线表、用例表、开题报告,用捷码AI一键生成

考务管理系统-综合设计成果/ ├── 00-交付清单/ manifest.json README ├── 01-系统图表/ 8 类系统图(E-R / 功能结构 / 数据流 / 架构 / 流程 / 类图 / 时序 / 用例) ├── 02-设计资料/ 数据库脚本 └── 03-交付成果/ … · 2026/11/5 7:53:51

毕设/课设别再熬夜画图了!SpringBoot监狱罪犯监管信息系统:功能结构图、流程图、数据流图、UML类图、时序图、用例图、三线表、用例表、开题报告,用捷码AI一键生成
毕设/课设别再熬夜画图了!SpringBoot监狱罪犯监管信息系统:功能结构图、流程图、数据流图、UML类图、时序图、用例图、三线表、用例表、开题报告,用捷码AI一键生成

监狱罪犯监管信息系统-综合设计成果/ ├── 00-交付清单/ manifest.json README ├── 01-系统图表/ 8 类系统图(E-R / 功能结构 / 数据流 / 架构 / 流程 / 类图 / 时序 / 用例) ├── 02-设计资料/ 数据库脚本 └── 03-交付… · 2026/11/5 7:53:51

移动应用性能评测:指标构建与优化实践
移动应用性能评测:指标构建与优化实践

1. 移动应用性能评测的行业现状 最近三年,国内移动应用月活用户增速已降至5%以下,但用户对应用性能的要求却越来越高。某第三方数据显示,2022年用户卸载应用的三大原因中,"卡顿闪退"占比达37%,仅次于"广… · 2026/11/5 8:35:15

同城社区配送小程序架构设计与优化实践
同城社区配送小程序架构设计与优化实践

1. 同城社区配送小程序的商业逻辑解析 "骑手抢单商家联动"的同城配送模式正在重构社区零售的最后一公里。这种O2O解决方案的核心在于建立了一个三方实时互动的交易平台:商家发布配送需求,骑手自主选择订单,用户享受即时送达服务。我… · 2026/11/5 8:35:15

ChatPDF文档问答:从PDF解析到混合检索的工程实践
ChatPDF文档问答:从PDF解析到混合检索的工程实践

1. ChatPDF 这类工具到底在替你做什么第一次看到“把 PDF 丢进去就能对话”这个形态,我的反应是:这不就是把文档塞进模型上下文吗,有什么难的。真动手做过两版之后才发现,难点从来不在“调模型”,而在于你怎么把一份几… · 2026/11/5 8:35:15

拆解PDF文档问答:解析、切片与混合检索的工程实践
拆解PDF文档问答:解析、切片与混合检索的工程实践

把一份 300 多页的设备验收规范丢进工具,问“第 4 章里那台机组的振动阈值是多少”,结果返回了另一份标准里的数值——这个场景我在过去一年里见过不下五次,提问的人有做工程的、有做法务的,也有写技术文档的。他们第一反应都是“… · 2026/11/5 8:35:15

社区配送小程序开发:抢单机制与LBS优化实践
社区配送小程序开发:抢单机制与LBS优化实践

1. 项目背景与核心价值在同城生活服务领域,社区配送一直是个高频刚需场景。我去年参与了一个社区配送小程序的完整开发周期,这个项目整合了商家端商品管理、骑手端抢单接单、用户端下单支付的全流程。相比传统的外卖平台,我们更聚焦3-5公里范… · 2026/11/5 8:35:15

GitHub+Arbess实现Java项目CI/CD自动化部署实战
GitHub+Arbess实现Java项目CI/CD自动化部署实战

1. 项目背景与核心价值 最近在团队内部落地了一套基于GitHub的Java项目自动化构建部署方案,用Arbess工具链实现了从代码提交到Docker容器部署的完整流水线。这套方案特别适合中小型团队快速搭建轻量级CI/CD环境,相比传统Jenkins方案节省了60%的运维成本。… · 2026/11/5 8:34:15

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 6:59:29

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 7:02:38

多智能体协作系统架构设计与实践优化
多智能体协作系统架构设计与实践优化

1. 多智能体协作系统的时代背景2017年Transformer架构的诞生彻底改变了人工智能的发展轨迹。当行业还沉浸在单一大模型带来的性能突破时,Anthropic的研究团队已经将目光投向了更前沿的领域——如何让多个智能体通过协作产生超越单体能力的系统智能。这就像交响乐团中… · 2026/11/5 0:00:39

大模型系统性入门实战指南:从原理到部署微调的全链路路线
大模型系统性入门实战指南:从原理到部署微调的全链路路线

提到大模型的系统性入门,我先说个结论:这事真不难,难的是资料太散、路线太多,今天这个框架明天那个工具,新人很容易在“收藏夹吃灰”和“教程看到一半放弃”之间反复横跳。市面上关于大模型的内容少说有几十万篇&#… · 2026/11/5 0:00:39

鸿蒙文件系统沙箱机制解析与开发实践
鸿蒙文件系统沙箱机制解析与开发实践

1. 鸿蒙文件系统沙箱机制深度解析作为一名从Android转向鸿蒙开发的工程师,我深刻体会到文件系统访问是迁移过程中最先遇到的"拦路虎"。在Android上运行良好的文件读写代码,在鸿蒙真机环境却频频出现文件写入后神秘消失或直接抛出权限拒绝错误的… · 2026/11/5 0:00:39

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 6:59:29

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 7:02:38

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码