网站开发前端好还是后端好,网站制作与建设教程下载,河北住房与建设信息网站,贵州seo技术查询换钱的方法数
【题目】 给定数组 arr#xff0c;arr 中所有的值都为正数且不重复。每个值代表一种面值的货币#xff0c;每种面值 的货币可以使用任意张#xff0c;再给定一个整数 aim#xff0c;代表要找的钱数#xff0c;求换钱有多少种方法。
【举例】 arr[5,10,25,1…换钱的方法数
【题目】 给定数组 arrarr 中所有的值都为正数且不重复。每个值代表一种面值的货币每种面值 的货币可以使用任意张再给定一个整数 aim代表要找的钱数求换钱有多少种方法。
【举例】 arr[5,10,25,1]aim0。 组成 0 元的方法有 1 种就是所有面值的货币都不用。所以返回 1。
arr[5,10,25,1]aim15。 组成 15 元的方法有 6 种分别为 3 张 5 元、1 张 10 元1 张 5 元、1 张 10 元5 张 1 元、10 张 1 元1 张 5 元、2 张 5 元5 张 1 元和 15 张 1 元。所以返回 6。 arr[3,5]aim2。 任何方法都无法组成 2 元。所以返回 0。
代码
public static int coins1(int[] arr, int aim) {if (arr null || arr.length 0 || aim 0) {return 0;}System.out.println(onWay(arr, 0, aim));System.out.println(onWay2(arr, 0, aim, new int[arr.length 1][aim 1]));return onWay3(arr,aim);}/*** 暴力递归* param arr* param i 可变参数位置下标* param rest 可变参数剩余金额* return*/public static int onWay(int[] arr, int i,int rest ) {if(i arr.length) {return rest0?1:0;}int count 0;for(int k 0;k*arr[i]rest;k) {count onWay(arr,i1,rest-k*arr[i]);}return count;}/*** 记忆化搜索* param arr* param i 可变参数位置下标* param rest 可变参数剩余金额* return*/public static int onWay2(int[] arr, int i,int rest ,int[][] map) {if(i arr.length) {return rest0?1:0;}int count 0;for(int k 0;k*arr[i]rest;k) {if(map[i1][rest-k*arr[i]] ! 0) {count map[i1][rest-k*arr[i]] -1?0:map[i1][rest-k*arr[i]];} else {count onWay2(arr,i1,rest-k*arr[i],map);}}map[i][rest] count0?-1:count;return count;}/*** 动态规划* param arr* param i 可变参数位置下标* param aim 可变参数剩余金额* return*/public static int onWay3(int[] arr, int aim) {int[][] dp new int[arr.length 1][aim 1];for(int i 0;iarr.length;i) {dp[i][0] 1;}for(int i 1;i*arr[0] aim;i) {dp[0][i*arr[0]] 1;}for (int i 1; i arr.length; i) {for (int j 1; j aim; j) {int nums 0;for(int k 0;j-k*arr[i] 0;k) {nums dp[i-1][j-k*arr[i]];}dp[i][j] nums;}}return dp[arr.length - 1][aim];}
