Dynamic programming: coin topic summary

1. arr Currency array , Where the values are integers . Give another integer aim, Each value is considered a currency , Even if the value of the same currency, it is considered that each one is different , return amin The number of ways

2. arr Currency array , Where the values are non repeating integers . Give another integer aim, The number of sheets per currency is unlimited , return amin The number of ways

3. arr Currency array , Where the value can be a repeating integer . Give another integer aim, Every identical value is considered to be the same currency , return amin The number of ways

4. arr Currency array , Where the values are non repeating integers . Give another integer aim, The number of sheets per currency is unlimited , Return composition aim Minimum number of sheets

From the trial model

From the trial code （ Trying to model leads to ）

public static int process(int[] arr, int index, int rest) {
    
	if (rest < 0) {
    
		return 0;
	}
	if (index == arr.length) {
     //  No money. ！
		return rest == 0 ? 1 : 0;
	}
	return  process(arr,index+1,rest)+process(arr,index+1,rest-arr[index]);
}

public static int process(int[] arr, int index, int rest) {
    
	if (index == arr.length) {
     
		return rest == 0 ? 1 : 0;
	}
	int ways = 0;
	for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
    
		ways += process(arr, index + 1, rest - (zhang * arr[index]));
	}
	return ways;
}

public static int process(int[] coins, int[] num, int index, int rest) {
    
	if (index == coins.length) {
    
		return rest == 0 ? 1 : 0;
	}
	int ways = 0;
	for (int zhang = 0; zhang * coins[index] <= rest && zhang <= num[index]; zhang++) {
    
		ways += process(coins, num, index + 1, rest - (zhang * coins[index]));
	}
	return ways;
}

public static int process(int[] arr, int index, int rest) {
    
	if (index == arr.length) {
    
		return rest == 0 ? 0 : Integer.MAX_VALUE;
	} else {
    
		int ans = Integer.MAX_VALUE;
		for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
    
			int next = process(arr, index + 1, rest - zhang * arr[index]);
			if (next != Integer.MAX_VALUE) {
    
				ans = Math.min(ans, zhang + next);
			}
		}
		return ans;
	}
}

from dp Watch , Try model code