换钱的方法数
【题目】
给定数组arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim代表要找的钱数，求换钱有多少种方法。
【举例】
arr=[5,10,25,1]，aim=0。
组成0元的方法有1种，就是所有面值的货币都不用。所以返回1。
arr=[5,10,25,1]，aim=15。
组成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]，aim=2。
任何方法都无法组成2元。所以返回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);
}
暴力递归 方法1 从前往后推
/**
* 换钱的方法数
*
* @author ZXQ
*
*/
public class Problem_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);
}
/**
*
* @param arr
* 面值组成的数值
* @param index
* 第几种钱
* @param aim
* 总钱数
* @return
*/
public static int process1(int[] arr, int index, int aim) {
int res = 0;
// 递归的终止条件 以5,3,2为例凑成10，5*1+3*1+2*1
// 此时循环index==arr.length，aim==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;
}
}
暴力递归 方法2 从后往前推
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;
}
实现准备好全局变量map记录已经计算过的递归过程的结果，防止下次重复计算。因为本题的递归过程课由 两个变量来表示，所以map是一张二维表，二维数组map[i][j]的结果代表p(i,j)的返回结果，在每一次进入下一次的递归之前，先查询是否已经计算过了，如果计算过就把结果从map中拿出来直接用，如果没计算过才进入递归过程，并且每个递归过程在计算完成后，都会将结果放入到map中，下次遇到相同的递归过程就可以防止重复计算了。其实记忆化搜索法可以认为是动态规划法。
动态规划逐步细化
如果arr长度为N，生成行数为N，列数为aim+1的矩阵dp，dp[i][j]的含义是在使用arr[0…i]的货币的情况下，组成钱数j有多少种方法，dp的求法如下：
1、对于矩阵dp第一列的值表示组成钱数为0的方法数，很明显是一种，即不适用任何货币，所以dp第一列的值统一设置为1，
2、对于dp矩阵第一行的值，表示只能使用arr[0]这一种货币情况下，组成钱的方法数，比如arr[0]=5时，能组成钱的数只能是0,5，10,15等等，也就是说arr[0]的整数倍的位置，才能被arr[0]这种货币组成，那么其他钱数就通通不行了，所以就将相应位置设置为1，而其他位置设置为0，
3、除了第一行第一列，其他位置假设为位置[i][j]，那么dp[i][j]的值是一下值的累加：
上面的方法数累加之后就是dp[i][j]的值，从左往右依次求出dp矩阵中每一行的值，然后再计算下一行的值，那么最终最右下角的值，即dp[N-1][aim]的值，就是最终结果，返回即可。
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];
}
main
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)");
}
测试结果
1103021
cost time : 826(ms)
1103021
cost time : 745(ms)
1070270201
cost time : 144(ms)
1070270201
cost time : 213(ms)
1070270201
cost time : 3(ms)
1070270201
cost time : 2(ms)
巴拉巴拉
自从一个月前加完一个大神之后，一直说要学习保持一周一博的节奏。
结果，整个假期各个学校跑野了，回校这几周来一直处于迷茫、焦虑、纠结的状态，总而言之，大四唯有认真体会，才能明白一些苦涩，选择又是如此艰难。
有人说我是矫情，有人说我身在福中不知福，而我都一笑置之。是时候踏实学习，恢复常态了。
看来左神的直播立马燃了，花了109块大洋买左神教程(有需要的微博私我)，肝疼~~~~~
“有的事道听途说的时候会觉得荒谬，仔细了解原委特别是身临其境以后，才有真正的判断。”–网上摘录
“生活不能等待别人来安排，要自己去争取和奋斗；而不论其结果是喜是悲，但是可以慰藉的是，你总不枉在这世上活了一场，有了这样的认识，你就会珍重生活，而不会玩世不恭，同时也给人自身注入一种强大的内在力量。”–《平凡的世界》路遥