动态规划
2021/6/6 10:51:02
本文主要是介绍动态规划,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
package advanced_class_06; public class Code_01_CoinsWay { public static int coins1(int[] arr, int aim) { if (arr == null || arr.length == 0 || aim < 0) { return 0; } return process1(arr, 0, aim); } public static int process1(int[] arr, int index, int aim) { int res = 0; if (index == arr.length) { res = aim == 0 ? 1 : 0; } else { for (int i = 0; arr[index] * i <= aim; i++) { res += process1(arr, index + 1, aim - arr[index] * i); } } return res; } /** * * @param arr * @param index * @param aim * @return */ public static int process2(int[] arr, int index, int aim) { int res = 0; if (arr.length == index) { res = aim == 0 ? 1 : 0; } else { for (int i = 0; arr[index] * i <= aim; i++) { res += process2(arr, index + 1, aim - arr[index] * i); } } return res; } public static int coinsOther(int[] arr, int aim) { if (arr == null || arr.length == 0 || aim < 0) { return 0; } return processOther(arr, arr.length - 1, aim); } public static int processOther(int[] arr, int index, int aim) { int res = 0; if (index == -1) { res = aim == 0 ? 1 : 0; } else { for (int i = 0; arr[index] * i <= aim; i++) { res += processOther(arr, index - 1, aim - arr[index] * i); } } return res; } public static int coins2(int[] arr, int aim) { if (arr == null || arr.length == 0 || aim < 0) { return 0; } int[][] map = new int[arr.length + 1][aim + 1]; return process2(arr, 0, aim, map); } public static int process2(int[] arr, int index, int aim, int[][] map) { int res = 0; if (index == arr.length) { res = aim == 0 ? 1 : 0; } else { int mapValue = 0; for (int i = 0; arr[index] * i <= aim; i++) { mapValue = map[index + 1][aim - arr[index] * i]; if (mapValue != 0) { res += mapValue == -1 ? 0 : mapValue; } else { res += process2(arr, index + 1, aim - arr[index] * i, map); } } } map[index][aim] = res == 0 ? -1 : res; return res; } public static int coins3(int[] arr, int aim) { if (arr == null || arr.length == 0 || aim < 0) { return 0; } int[][] dp = new int[arr.length][aim + 1]; for (int i = 0; i < arr.length; i++) { dp[i][0] = 1; } for (int j = 1; arr[0] * j <= aim; j++) { dp[0][arr[0] * j] = 1; } int num = 0; for (int i = 1; i < arr.length; i++) { for (int j = 1; j <= aim; j++) { num = 0; for (int k = 0; j - arr[i] * k >= 0; k++) { num += dp[i - 1][j - arr[i] * k]; } dp[i][j] = num; } } return dp[arr.length - 1][aim]; } public static int coins4(int[] arr, int aim) { if (arr == null || arr.length == 0 || aim < 0) { return 0; } int[][] dp = new int[arr.length][aim + 1]; for (int i = 0; i < arr.length; i++) { dp[i][0] = 1; } for (int j = 1; arr[0] * j <= aim; j++) { dp[0][arr[0] * j] = 1; } for (int i = 1; i < arr.length; i++) { for (int j = 1; j <= aim; j++) { dp[i][j] = dp[i - 1][j]; dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0; } } return dp[arr.length - 1][aim]; } public static int coins5(int[] arr, int aim) { if (arr == null || arr.length == 0 || aim < 0) { return 0; } int[] dp = new int[aim + 1]; for (int j = 0; arr[0] * j <= aim; j++) { dp[arr[0] * j] = 1; } for (int i = 1; i < arr.length; i++) { for (int j = 1; j <= aim; j++) { dp[j] += j - arr[i] >= 0 ? dp[j - arr[i]] : 0; } } return dp[aim]; } public static void main(String[] args) { int[] coins = { 10, 5, 1, 25 }; int aim = 2000; long start = 0; long end = 0; start = System.currentTimeMillis(); System.out.println(coins1(coins, aim)); end = System.currentTimeMillis(); System.out.println("cost time : " + (end - start) + "(ms)"); start = System.currentTimeMillis(); System.out.println(coinsOther(coins, aim)); end = System.currentTimeMillis(); System.out.println("cost time : " + (end - start) + "(ms)"); aim = 20000; start = System.currentTimeMillis(); System.out.println(coins2(coins, aim)); end = System.currentTimeMillis(); System.out.println("cost time : " + (end - start) + "(ms)"); start = System.currentTimeMillis(); System.out.println(coins3(coins, aim)); end = System.currentTimeMillis(); System.out.println("cost time : " + (end - start) + "(ms)"); start = System.currentTimeMillis(); System.out.println(coins4(coins, aim)); end = System.currentTimeMillis(); System.out.println("cost time : " + (end - start) + "(ms)"); start = System.currentTimeMillis(); System.out.println(coins5(coins, aim)); end = System.currentTimeMillis(); System.out.println("cost time : " + (end - start) + "(ms)"); } }
这篇关于动态规划的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)