Java实现 LeetCode 322 零钱兑换
2023-09-14 08:58:05 时间
322. 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。
class Solution {
private int min = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
Arrays.sort(coins); // asc
dfs(coins, coins.length - 1, amount, 0);
return min == Integer.MAX_VALUE ? -1 : min;
}
private void dfs(int[] coins, int ci, int rest, int cnt) {
if (ci < 0) return;
for (int i = rest / coins[ci]; i >= 0; i--) {
int currRest = rest - i * coins[ci], currCnt = cnt + i;
if (currRest > 0 && currCnt + 1 < min) dfs(coins, ci - 1, currRest, currCnt);
else {
if (currRest == 0 && currCnt < min) min = currCnt;
break;
}
}
}
}
相关文章
- java单例模式_Java单例模式
- java游戏开发入门教程_JAVA制作游戏入门教程
- java dom4j生成xml格式化_Java DOM4J方式生成XML的方法「建议收藏」
- JAVA的使用_Java集成开发环境
- Java 8 的 java.util.function.* POJO 的反射新方法
- java h2 数据库_Java H2数据库
- Java操作MySQL数据库快速入门(java访问mysql)
- 解决Java程序连接MySQL的准确方案:Java连接MySQL的Jar包(java连接mysql的jar包)
- 数据库Java实现Oracle数据库监控(java监听oracle)
- 服务器实现Java远程访问Linux服务器(java远程linux)
- 玩转Linux:Java开发入门指南(linux上开发java)
- Linux下安装Java的简易步骤(linux如何安装java)
- Java脚本实现Linux系统的登录(java登录Linux)
- Java中使用Redis包实现高效缓存(redis包java)
- 使用Java连接MySQL实现查询功能(java连接mysql查询)
- 实现Java实现Redis锁的研究与应用(redis锁java)
- Java与Linux:前景迷人的新科技(java和linux前景)
- Linux平台上C语言接口调用Java语言实现(linux c调java)
- 管理Linux下Java版本管理:轻松实现多版本切换(linux下java版本)
- Java搭配MySQL,实现创新跳跃的可能(java 与mysql)
- 在Linux上实现Java程序的运行(linux运行java程序)
- Java模拟Oracle实现稳定数据库性能(java模仿oracle)
- 提升Java工程师技术Oracle搭配Java的绝佳美妙(java搭配oracle)
- Java使用Oracle实现优雅数据查询(java.oracle)
- Oracle中实现Java程序设计的极限可能性(oracle中的java)
- 并发Redis锁保障Java并发性(redis锁实现java)
- 实现基于Redis的分布式锁Java实现(redis锁java代码)