Dynamic programming example 1 leetcode 322 coin change

Translation work

Give you an array , Elements represent coins of different denominations , An integer , Represents the total amount of money . Round up the total amount of money with the fewest coins , If the total amount cannot be rounded up, return -1.

You may need to give a specific set of denominations ;

Example 1：

Input ：coins = [1,2,5],amount =11

Output ：3

explain ：11=5+5+1

Example 2：

Input ：coins = [2],amount = 3

Input ：-1

Example 3：

Input ：coins = [1],amount = 0

Output ：0

methodology ：

With coins=[2,5,7],m=27 For example

1. Determine the state of

Array f[i]/f[i][j] What is the ？

​​ Make sure the status has 2 Consciousness ：1） The last step 2） Sub problem

1） The last step

Suppose the optimal strategy is K A coin consists of , namely a1,a2,a3,……ak,a1+……ak = 27

27-ak	ak
K-1 Coin	The last one

notes ：2 The key

a. I don't care how to spell the coins in front 27-ak Of （ Probably 1 Maybe 100 Kind of ）, I don't even know ak and K, But I'm sure the front coin spelled 27-ak.

b. Because it's the best strategy , So spell out 27-ak The number of coins must be the optimal solution .

2) Sub problem

With the fewest coins you can spell 27-ak.

set up f[x] It means to spell the least coin x,ak The value is 2,5,7,m=27

f[27] The value of may be f[27-2]+1,f[27-5]+1,f[27-7]+1, From the question

f[27] = min{ f[27-2]+1,f[27-5]+1,f[27-7]+1}

2. Transfer equation

f[x] Means to spell x The minimum number of coins

For any x, Yes f[x] = min{ f[x-2]+1,f[x-5]+1,f[x-7]+1}

3. Initial conditions , Boundary situation

f[0] = 0,f[x] = Positive infinity means that the current coin cannot be spelled x

4. Computation order

initial f[0] = 0

Calculation f[1],f[2]……f[27]

Example

#include<iostream>
#include<malloc.h>

using namespace std;

//LintCode;Coin Change
//3 Grow coins 2 element  5 element  7 element , Buy a Book 27 element 
// How to pay with the least combination of coins , There is no need for the other party to pay f(x) Said to buy one 27 Yuan book to make up the least coin 


/******66656565{2,5,7} ***  27*/
int CoinChange(int A[], int m) {
	int MAXN = 32001;
	int *f = new int[m+1];
	f[0] = 0;
	int lenA = 0;
	for (int i = 0; A[i] >= 0; i++) {
		lenA++;
	}
	int i, j;
	for (i = 1; i <= m; i++) {  //1 2 3...m
		f[i] = MAXN;
		for ( j = 0; j < lenA; j++) {  //2 5 7
			if (i >= A[j] && A[i - A[j]] != MAXN) { // The required amount is greater than the face value and the current face value can make up the required amount 
				f[i] = f[i] < (f[i - A[j]] + 1) ?  f[i] : (f[i - A[j]] + 1) ;
			}
		}
	}
	if (f[m] == MAXN) {
		f[m] = -1;
	}
	return f[m];
}

int main() {
	//Coinchange
	int A[] = { 2,5,7 };
	int m = 27;
	cout<<CoinChange(A,m);
	return 0;
}