What is dynamic programming

Last time we had a general analysis of dynamic programming. To quote Wikipedia: dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems

Dynamic programming is a way of solving complex problems by breaking them down. So we also know that the core of dynamic programming is how to split the problem and how to split the problem is going to be the focus of our research. For reference, most authorities agree with the view that the resolution of the problem depends on the definition of the state and the definition of the state transition equation. Here are zhihu again is a view of the above definition: www.zhihu.com/question/23…

What is the definition of state

Our definition of state is as follows: to solve the dynamic programming problem, we need to open an array of what each element in the array f[I] or f[I][j] represents. The definition of status requires two steps: 1. 2. Sub-issues.

Topic describes

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example Given coins = [1, 2, 5], amount = 11 return 3 (11 = 5 + 5 + 1)

Given coins = [2], amount = 3 return -1.

Notice You may assume that you have an infinite number of each kind of coin.

Simple explanation of the problem: the existing coins of different currency value, make up a given amount, can not be more or less, the least number of coins; If there is no solution, -1 is returned.

Their thinking

So let’s go back to the two steps of the definition of state. Final step:

1,2,5 coins make up 11 dollars. Let’s say the optimal strategy is k coins make up 11 dollars, and the last coin is worth a (k) dollars, so the first coin is spelled out to be worth 11- A (k) dollars, and that’s the definition of the state to do the last step first. And then from the subproblem: since we have defined it from the last step, to convert the original problem to another problem is to make up 11-a (K) yuan with the smallest number of coins, then reduce the original size, and then the problem is a subproblem of the original problem. We can define how many yuan to make up (the scale) as X, then we can make up X yuan by using state F (X) = making up X yuan with the fewest coins. Let’s say the last coin is 1, then f(11) = f(11-1)+1; If the last one is 2, then f(11) = f(11-2)+1; In the same way, the last one to five, then the f (11) = f (11-5) + 1, is actually the least amount of COINS to f (11) = min {f (11-1) + 1, f (11-2) + 1, + 1} f (11-5). We can express this programmatically:

Int f(x){int f(x){if(x==0)return 0;
int res = Integer.MAX_VALUE;
if(x>=1){
res = Math.min(f(x-1)+1,res);
}
if(x>=2){
res = Math.min(f(x-2)+1,res);
}
if(x>=5){
res = Math.min(f(x-5)+1,res);
}
return res;
}
Copy the code

But the recursive method does a lot of repeated calculation, such as F (9)-> F (11-1)->f(10-9) or F (11-2) can be calculated. At this point we can turn to the second part of dynamic programming, state transitions.

So it’s very simple to take f of x and turn it into an array f[x] and store the result. F [x]=min{f[x-1]+1,f[x-2]+1,f[x-5]+1} Since it’s an array, we should worry about lower bounds and initial values. If we can’t spell out a value like f[-1] or f[-3], we define it as a positive infinity Max_Value, and the initial value f[0]=0 means that there are zero coins to spell out. At this point we should be raised to the minimum order to calculate each element hard currency, namely: f [1] = min {f] [1-1 + 1, + 1 f [1-2], [1-5] f + 1} [0] = f + 1 = 1

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

It is not difficult to find that, when F [2] takes 1 piece as the last coin, f[1] has actually saved the minimum number of coins with this value without repeated calculation, and the algorithm time degree is X*3

Take a look at the program:

public int coinChange(int[] a, int M) { // write your code here int length = a.length; int []f = new int[M+1]; // initialize f[0]=0;for(int i=1; i<=M; F [I]= integer.max_value; f[I]= integer.max_value;for(int j=0; j<length; J++){// the sum must be greater than the value of the coin and the coin should not equal infinityif(i>=a[j]&&f[i-a[j]]! =Integer.MAX_VALUE&&f[i-a[j]]+1<f[i]){
                    f[i]= f[i-a[j]]+1; }}}if(f[M]==Integer.MAX_VALUE){
            return- 1; }else {
            returnf[M]; }}Copy the code

Author’s brief introduction

Rowland, the koala’s backend developer, loves sports and is a little cute!