Today’s sharing started, please give us more advice ~
4 – step routine to solve the dynamic programming problem
1. Determine the problem state and refine the problem transformation in the last step
2, transfer the equation, the problem equations
3. Set initial conditions and boundary cases according to actual logic
4. Determine the calculation sequence and solve
Combined with examples to feel:
You have three coins worth $2, $5 and $7, and enough of each. It costs 27 yuan to buy a book. How do I pay off with the fewest combinations of coins and not get change?
Key words “Pay off exactly with the smallest combination of coins” — “minimum combination”, optimal problem, dynamic programming.
** Normal people’s first thought :** minimum coin combination? Prefer large coins – 7+7+7+5=26? The solvable target is 27… We changed the algorithm — 7+7+7+2+2+2=27, and we used 6 coins to get exactly 27 yuan. The actual answer: 7+5+5+5+5=27, using only 5 coins. So the greedy algorithm here is not correct.
Routine use:
The first step is to determine the problem state.
To solve the dynamic programming problem, we need to first open an array and determine what each element of the array f[I] represents, which is to determine the state of the problem. It’s like figuring out what X, Y, and Z stand for in math.
A. Determine the state first extraction [Last step]
The optimal strategy must be K coins a1, A2… AK values add up to 27.
Find the last independent role that does not affect the optimal strategy. In this case, the last coin “aK” is the last step. If aK is extracted, the value of all coins before aK is always 27-AK plus 27-AK. Because of the strategy of minimizing the number of coins, the number of coins that spell 27-AK must be the least (important setting).
B, ** transformation subproblem. ** After the aK is presented in the last step, we just need to figure out “the minimum number of coins needed to spell 27-AK”.
Such problems, which have the same kernel as the original problem but are smaller in size, are called subproblems.
To simplify the definition, let’s say that state F (X)= the minimum number of coins needed to spell out the total face value X. We don’t yet know how the aK will end up, but it’s likely to be one of 2/5/7.
If aK is 2, f of 27 would be f of 27 minus 2 plus 1 if aK is 5, f of 27 would be F of 27 minus 5 plus 1 if aK is 7, F of 27 is going to be f of 27 minus 7 plus 1, plus the last 7 coin, but there’s no other way.
At this point, by finding the last step of the original problem, and transform it into a sub-problem. The state of finding the minimum number of coin combinations for the total value of 27 is formed, expressed as the following function:
f(27) = min{f(27-2)+1, f(27-5)+1, f(27-7)+1}
The second step is to transfer the equation and make the problem equations.
F [X] = min{f[x-2]+1, f[x-5]+1, f[x-7]+1}
Solving dynamic programming problems in the actual interview, correctly listing the correct transfer equation is basically half the solution.
But ask me: how is this different from recursion?
A recursive solution:
// Xint f(int X) {// if (X == 0) return 0; // Initialize with infinity. int res = MAX_VALUE;
If (X >= 2) {res = math.min (f(X — 2) + 1, res); } / / 5 yuan is the last coin if (X > = 5) {res = Math. Min (f (X – 5) + 1, res); } / / the last coin is 7 yuan if (X > = 7) {res = Math. Min (f (X – 7) + 1, res); }return res; }
The execution diagram is as follows:
To calculate f(27), we recurse f(25), f(22), f(20), and then recurse down… (triangle).
The problem is obvious — too many repetitions.
This is f(27), and you can still recurse. What about f of 100? It’s astronomical. The end result is a recursive supermarket.
To maximize the population, always prioritize dynamic programming over silly recursion.
Third, set the boundary cases and initial conditions according to the actual logic.
** Otherwise, even if the transfer equation is correct, there is a large probability that the code will not run.
F (X) = min {f/X – 2 + 1, f/X – 5 + 1, f [X] + 1} boundary condition is [X – 2] / [X – 5] / [X] cannot be less than zero (COINS face value is positive), nor more than 27.
Therefore, the boundary case is set as follows:
If Y cannot be combined, define f[Y]= infinity e.g. F [-1]=f[-2]=… = plus infinity; F [1] =min{f[-1]+1, f[-4]+1,f[-6]+1}= positive infinity,
** Special case: ** in this case, the corresponding case of F[0] is F[-2], F[-5], F[-7], and the result is positive infinity according to the boundary case above.
But in fact the result of F[0] exists (that is, if 0 coins are used), F[0]=0. But F[0]=F[0-2]+1= F[-2]+1= infinity.
Is it not a contradiction?
Such cases, which cannot be calculated by the transfer equation, but exist, must be defined manually.
The initial condition is manually enforced: F[0]=0.
F[1]= F[1-2]+1= F[-1]+1= infinity (infinity plus any number is infinity); F [2] = F (2, 2] [0] + 1 + 1 = F = 1…
The fourth step, determine the order of calculation and calculate the solution
So what if I start with F[1], F[2]? Or start with F[27] and F[26]?
The principle to judge whether the order of calculation is correct is that when we want to calculate F[X] (the left side of the equation, such as F[10]), the right side (F[x-2], F[X-5], F[x-7], etc.) are all in the state of obtaining the result, so the order of calculation is OK.
It’s actually going from small to large (with some exceptions we’ll talk about later).
For example, when we calculate F[12], we find that F[11], F[10] and F[9] have been calculated, so this algorithm is correct. When we start to calculate F[27], we find that F[26] has not been calculated, so the order is wrong.
Obviously a FOR loop is enough in this case.
Going back to this problem, using the dynamic programming algorithm, we only tried three coins at each step, and we did 27 steps. The algorithm’s time complexity (i.e. the number of steps required) is 27*3.
In contrast to recursion, there is no double calculation.
** This is a Coin Change problem with LintCode number 669. The code is as follows:
Public int coinChange(int[] A, int M){// A = [2,5,7]// M = 27int[] f = new int[M + 1]; int n = A.length; F [0] = 0; f[0] = 0; // f[1], f[2], … , f[27] = Integer.MAX_VALUEfor (int i = 1; i <= M; i++){f[i] = Integer.MAX_VALUE; }for (int i = 1; i <= M; I++) {/ / use the first coin A [j] j / / f [I] = min {f [I – A [0]] + 1,… , f[i-A[n-1]]+1}for (int j = 0; j < n; ++j)
{/ / if the through put the COINS to weight the iif (I > = A [j] && f [I – A [j]]. = integer.max_value) {// The number of coins that get the weight of I is the same as the number of coins that get the weight of i-a [j]. Math. Min (f[I]] + 1, f[I]); }}}if (f[M] == Integer.MAX_VALUE){return -1; }return f[M]; }
Conclusion:
1. This is the optimal problem, solved by dynamic programming.
2, enter the solution process, first determine the problem state.
Refine the last step (the last coin used in the optimal strategy aK)
– Subproblem conversion (fewest coins spell smaller denominations 27-AK)
3. Construct the transfer equation f[X] = min{f[x-2]+1, F [x-5]+1, F [x-7]+1}
(Min because they want to minimize it)
4, set the initial conditions and boundary case f[0] = 0, if Y cannot be spelled, f[Y]= positive infinity
5. Determine the calculation sequence and calculate and solve
F [0], f [1], [2] f…
In fact, according to the above 4 steps, basically can deal with the absolute majority of dynamic planning interview questions.
conclusion
Since I choose this industry and choose to be a programmer, I understand that only by constantly learning and accumulating practical experience can I be qualified to go up and get a high salary. I can have certain economic security for myself, my parents and my family in the future.
Learning time is squeezed out of their own, a short time may be difficult to see the effect, once adhere to down, will inevitably change. Think about why you want to get into this industry and give yourself an answer.
Interview big factory, the most basic is to tamp solid foundation, otherwise the interviewer casually ask you cool; Will ask some technical principle next, still can see you to the breadth of knowledge mastery, the most important or your train of thought, this is the interviewer more value.
Finally, the above big factory interview real questions are very good learning materials, through the interview real questions to see their technical knowledge to grasp the general situation, so as to be able to set a learning direction for themselves.
Today’s share has ended, please forgive and give advice!