递归DP-找零钱的方法数
package com.jiucaiyuan.net.question; /** * 找零钱的方法数 * 给定一个数组,表示总共有币种的面值,(不重复的正数数组) * 再给定一个金额数aim,问题是有多少种钱币的组合,可以正好满足指定金额(某一个金额的钱币张数不限) * * @Author jiucaiyuan 2022/6/12 14:31 * @mail services@jiucaiyuan.net */ public class ChangeMethod { /** * @param arr arr都是正数,没有重复值,每个面值代表一个货币,每一种都可以用无限张 * @param aim 要找零钱数 * @return 组合找零钱的方法数 */ public static int way1(int[] arr, int aim) { return process(arr, 0, aim); } /** * 可以自由选择使用arr中index后所有的面值 * 剩余需要组合的钱币数是rest * * @param arr * @param index * @param rest * @return */ public static int process(int[] arr, int index, int rest) { if (index == arr.length) { return rest == 0 ? 1 : 0; } int ways = 0; for (int count = 0; arr[index] * count <= rest; count++) { ways += process(arr, index + 1, rest - arr[index] * count); } return ways; } /** * 时间复杂度 O(N*aim*aim)) * * @param arr * @param aim * @return */ public static int way2(int[] arr, int aim) { if (arr == null || arr.length == 0) { return 0; } int N = arr.length; int[][] dp = new int[N + 1][aim + 1]; dp[N][0] = 1; for (int index = N - 1; index >= 0; index--) { for (int rest = 0; rest <= aim; rest++) { int ways = 0; for (int count = 0; arr[index] * count <= rest; count++) { ways += dp[index + 1][rest - arr[index] * count]; } dp[index][rest] = ways; } } return dp[0][aim]; } /** * way2基础上做斜率优化,当前可以通过前一个进行计算,没必要做枚举的累计 * 从way2的得到值的规律中观察得到 * * @param arr * @param aim * @return */ public static int way3(int[] arr, int aim) { if (arr == null || arr.length == 0) { return 0; } int N = arr.length; int[][] dp = new int[N + 1][aim + 1]; dp[N][0] = 1; for (int index = N - 1; index >= 0; index--) { for (int rest = 0; rest <= aim; rest++) { //一个位置总是需要自己下方的格子 dp[index][rest] = dp[index + 1][rest]; if (rest - arr[index] >= 0) { //一个位置总是需要自己下方的格子外,还需要自己本行-一个面值的格子的值 dp[index][rest] += dp[index][rest - arr[index]]; } } } return dp[0][aim]; } //for test public static int[] generateRandomArray(int length, int max) { int[] arr = new int[(int) (Math.random() * length) + 1]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) (Math.random() * max) + 1; } return arr; } public static void main(String[] args) { int len = 10; int max = 10; int testTimes = 100000; for (int i = 0; i < testTimes; i++) { int[] arr = generateRandomArray(len, max); int amount = (int) (Math.random() * 3 * max) + max; int ways = way1(arr, amount); System.out.println("------------------------------" + i + "--------" + ways); System.out.println(print(arr) + "<----->" + amount); if (ways != way2(arr, amount) || ways != way3(arr, amount)) { System.out.println("goooooooood!"); break; } } } private static String print(int[] arr) { StringBuffer sb = new StringBuffer(); for (int a : arr) { if (sb.length() == 0) { sb.append("[").append(a); } else { sb.append(",").append(a); } } sb.append("]"); return sb.toString(); } }
日历
个人资料
![blogger](http://www.jiucaiyuan.net/content/uploadfile/201509/thum-623a1441115314.jpg)
diaba 寻求合作请留言或联系mail: services@jiucaiyuan.net
链接
最新文章
存档
- 2024年8月(2)
- 2024年6月(4)
- 2024年5月(1)
- 2023年7月(1)
- 2022年10月(1)
- 2022年8月(1)
- 2022年6月(11)
- 2022年5月(6)
- 2022年4月(33)
- 2022年3月(26)
- 2021年3月(1)
- 2020年9月(2)
- 2018年8月(1)
- 2018年3月(1)
- 2017年3月(3)
- 2017年2月(6)
- 2016年12月(3)
- 2016年11月(2)
- 2016年10月(1)
- 2016年9月(3)
- 2016年8月(4)
- 2016年7月(3)
- 2016年6月(4)
- 2016年5月(7)
- 2016年4月(9)
- 2016年3月(4)
- 2016年2月(5)
- 2016年1月(17)
- 2015年12月(15)
- 2015年11月(12)
- 2015年10月(6)
- 2015年9月(11)
- 2015年8月(8)
分类
热门文章
- SpringMVC:Null ModelAndView returned to DispatcherServlet with name 'applicationContext': assuming HandlerAdapter completed request handling
- Mac-删除卸载GlobalProtect
- java.lang.SecurityException: JCE cannot authenticate the provider BC
- MyBatis-Improper inline parameter map format. Should be: #{propName,attr1=val1,attr2=val2}
- Idea之支持lombok编译
标签
最新评论
- logisqykyk
Javassist分析、编辑和创建jav... - xxedgtb
Redis—常见参数配置 - 韭菜园 ... - wdgpjxydo
SpringMVC:Null Model... - rllzzwocp
Mysql存储引擎MyISAM和Inno... - dpkgmbfjh
SpringMVC:Null Model... - tzklbzpj
SpringMVC:Null Model... - bqwrhszmo
MyBatis-Improper inl... - 乐谱吧
good非常好 - diaba
@diaba:应该说是“时间的度量依据”... - diaba
如果速度增加接近光速、等于光速、甚至大于...
最新微语
- 从今天起,做一个幸福的人。喂马,砍柴,(思想)周游世界
2022-03-21 23:31
- 2022.03.02 23:37:59
2022-03-02 23:38
- 几近崩溃后,找到解决方法,总是那么豁然开朗!所以遇到问题要坚持!
2018-07-18 10:49
- 2018年关键字“走心”
2018-03-19 16:07
- 保护好自己最大的方法是让自己更强大,不要柔弱的像一只绵羊一样,得谁巴拉,就谁巴拉!
2017-12-20 10:24
发表评论: