Remember a chance to see a JS problem, their first difficult to understand, convenient memory record, already familiar with please ignore

Description: Give coins of different denominations and an amount. Write a function to calculate the minimum number of coins needed to make up the total. If no one coin combination makes up the total, return -1

Example 1: Input: Coins = [1, 2, 5], amount = 11 Output: 3 Description: 11 + 5 + 1 Example 2: Input: Coins = [2], amount = 3 Output: -1Copy the code

The answer is here

const coinChange = function (coins, amount) { const f = []; f[0] = 0; for (let i = 1; i <= amount; i++) { f[i] = Infinity; for (let j = 0; j < coins.length; J++) {if (I - COINS [j] > = 0) {/ / state transfer equation f [I] = math.h min (f [I], f [I - COINS [j]] + 1); } } } if (f[amount] === Infinity) { return -1; } return f[amount]; };Copy the code

Although I saw the answer and verified that it was true, I just didn’t understand. I wanted to understand why I recorded the parsing process

The state transition equation is the result of the state in the previous stage and the decision in the previous stage. If the state Sk of stage K and the decision UK (Sk) are given, then the state Sk+1 of stage K+1 is completely determined.

Dynamic transition equation definition: in dynamic programming, the state at this stage is often the result of the state at the previous stage and the decision at the previous stage. Given the K phase state Sk and the decision UK (Sk), the K+1 phase state Sk+1 is also completely determined. In other words, there is a definite quantitative correspondence between Sk+1 and Sk, UK, denoted as Tk(Sk, UK), i.e. Sk+1= Tk(Sk, UK). This kind of equation is called state transition equation. In the above example, the state transition equation is Sk+1= UK (Sk).

Just see this explanation is not understand, later more see more flavor, is a novice vernacular

We can print the f array, which records the minimum number of each item from 0 to amount

when

coinChange([2],6)
Copy the code

When f array is yes

[ 0, Infinity, 1, Infinity, 2, Infinity, 3 ]
Copy the code

Amount =1 f[1] Infinity when amount=2 f[2] 1 when amount=3 f[3] Infinity when amount=4 f[4] 2 when amount=5 f[5] Infinity When amount=5 corresponds to f[6] 3

I-coins [j] >= 0; if i-coins is less than or equal to the sum, then there are no i-coins at all. For (let j = 0; f[I]] = 0; f[I] = 0; f[I] = 0; j < coins.length; The j++) loop is replaced with the smallest + 1 because one of coins is eliminated, and the total number of coins is calculated by adding the smallest remaining value to the one removed. Because the f array keeps track of everything, you can derive from it. Write a few more numbers to derive and figure out.