There are certain rules to follow, find routines.

What is dynamic programming?

How many ways are there to get to the bottom right (this is where you can use dynamic programming) output all the paths to the bottom right (DFS recursion)

Topic classification:

  1. How many ways can I count to get to the bottom right how many ways can I pick K numbers so that the sum is sum
  2. Find the maximum and minimum value of the path from the lower left corner to the lower right corner and the longest ascending subsequence length
  3. In the existential pebble picking game, is the first hand going to win and can we pick K numbers such that the Sum is Sum

coin change

There are 3 coins, denominations :2 yuan,5 yuan,7 yuan, enough of each coin

It costs 27 yuan to buy a book.

How to use the fewest combinations of coins to pay off exactly, without change.

Forget dynamic programming for a moment: Intuition: try to use large coins, and eventually pay with one coin if you can.

Dynamic 4 steps:

1. Determining the status (Calming the mind)

  • Solving dynamic programming requires opening an array, where each element f[I] or f[I][j] represents what

    • It’s kind of like figuring out what X,Y,Z stands for in math.

  • Determining a state requires two meanings:

    • The last step

      • I don’t know what the optimal strategy is, but the optimal strategy must be K coins a1, A2,…., right Ak values add up to 27
      • So there must be a final coin: AK
      • Excluding this coin, the face value of the front coins adds up to 27-AK
      • We don’t care how the K-1 coin spells 27-AK (maybe 1 spelling, maybe 100 spellings), and we don’t even know ak and K yet, but we do know that the previous coin spells 27-AK (last step, there’s a certain amount of uncertainty).
      • The key: because it’s the optimal strategy, because the number of coins that spell 27-AK has to be minimal, otherwise it’s not optimal. Regardless of the last coin, the spelling of the remaining coins is also optimal.

    • Subproblems:

      • Thus, the minimum number of coins needed to spell 27-AK
      • The original question was how many coins to make 27
      • We converted the original problem into a subproblem of a much smaller size: 27-AK
      • Just to simplify the definition, let’s say that f of X is equal to the minimum number of coins needed to spell X

    • Even after analyzing the last step, and the subproblems, we still don’t know what ak is the last coin

    • The last coin ak could only be 2,5,7

      • If AK is equal to 2,f of 27 is equal to f of 27 minus 2 plus 1
      • If AK is equal to 5,f of 27 is equal to f of 27 minus 5 plus 1
      • If AK is equal to 7,f of 27 is equal to f of 27 minus 7 plus 1
      • There is no other possibility.
      • Minimum number of coins required:
      • f(27) = min{f(27-2)+1,f(27-5)+1,f(27-7)+1} +1

Recursive solution:

Recursive algorithm analysis:

  • F of 20 is repeated three times
  • F (15) is repeated twice

Results:

There’s a lot of redundant double computing, which is inefficient.

How to avoid it?

  1. Save the results
  2. And change the order of calculation.

2. Transfer equation

  • Set state f[X] = the minimum number of coins to spell X (square brackets are arrays)
  • For any X:
  • At this point, the dynamic programming problem is half solved.

3. Initial conditions and boundary problems

After the transfer equation is determined, the initial conditions and boundary problems need to be determined.

  • f[27] = min{f[27-2]+1,f[27-5]+1,f[27-7]+1} +1
  • Two questions: what if X minus 2,X minus 5, or X minus 7 is less than 0? When does it stop?
  • If you can’t spell Y, define f[Y]= plus infinity
    • For example, f[-1]=f[-2]= infinity
    • In practice, you don’t really open f[-1]
  • So f [1] = min {f + 1 [1], [4] + 1 f, f + 1} [6] = is infinite, said couldn’t spell the one
  • Initial conditions: f[0] = 0

4. Determine the order of calculation

  • Initial conditions: f[0]= 0
  • Then f[1], F [2],f[3]…. are calculated in ascending order (Generally incremental calculation)
  • Benefits: but when we calculate f [X], [2] X, f f [5] X, f [X] have got a result, to avoid the repeated calculation

Time complexity:

O(n)= n

Conclusion:

  1. Dynamic programming is preferred for optimal types.
  2. Determine the state of
    • Final step: ak, the last coin used in the optimal strategy
    • This translates into a subproblem: the fewest coins spell 27-AK
  3. Determine the transfer equation: F [X] = min{f[x-2]+1, F [X-5]+1, F [X-7]+1} +1
  4. Determine initial conditions and boundary cases: f[0]=0; I can’t spell F[X] = infinity
  5. Determine the calculation order: F [0]–> F [1]–>f[2]….

My didi Cloud exclusive AI master code: 3388, buy Didi Cloud GPU and other AI products enter the master code to enjoy a 10% discount. Click www.didiyun.com to go to the official website of Didi Cloud to buy

This article was automatically published by ArtiPub