By the way, our official account has at least a dozen of articles which disassemble the problem of dynamic programming, all of which I have merged into the [list of articles] , **they all mention the problem solving framework of dynamic programming， we systematically summarize that**. During this period, I have grown from a non class of computer science to who has completed more than half of the LeetCode, so what I summarize may not be suitable for every master, but for the public, after all I hustle all the way.

There are a few set-pieces for algorithm skills, if you know, you will get a lot easier, this articles aims to see through dynamic programming and form a framework to solve this series of problems. Let's get into the straight point, here are the full contents.

Firstly, the enumeration of dynamic programming is a bit special, because there **exists [overlapped subproblems]** this kind of problems have extremely low efficiency, we need [memos] or [DP table] to optimize the process of enumeration to avoid unnecessary calculations.

And that, the DP problems must **have [best substructure]** , only through the max or min of subproblems can we obtain the max or min of original problems.

Moreover, although the core idea of DP is to enumerate for max or min, the problem itself varies, to enumerate all feasible answers is not a easy thing, only when listing the **correct [state transition equation]** can we enumerate perfectly.

Now, draw the recursive tree, and you will know what [memo] does.

In fact, recursive algorithms together with [memos], put a recursive tree with abundant redundancy through [pruning], we change one recursive graph without redundancy, which intensely decreases the number of subproblems (namely the node in recursive graph)

Therefore, the time complexity of this algorithm is O(n).Instead of a brute-force algorithm, it's a dimension reduction attack.

For example, your original problem is to get the highest total score, then your sub-problem is to get the highest Chinese test, mathematics test to the highest......In order to get the highest score in each subject, you need to get the highest multiple choice score for each subject and the highest fill-in-the-blank score...Of course, the end result is that you get full marks for each course, which is the highest total score.

So, now that you know that this is a dynamic programming problem, you have to think about

**how do you get the right transition equation**?

**first determine the "state" **, which is the variable that changes in the original problem and subproblems. Since the number of COINS is infinite, the only state is the target amount 'amount'.

**then determine the definition of the 'dp' function ** : the current target amount is' n ', at least 'dp(n)' COINS are needed to make up the amount.

**then determine the "choice" and choose the best **, that is, for each state, what choices can be made to change the current state. Specific to this problem, no matter what the target amount is, the choice is to choose a coin from the denomination list 'COINS', and then the target amount will be reduced:

So far, the state transfer equation has been completed, and the above algorithm is already a violent solution. The mathematical form of the above code is the state transfer equation:

Without drawing, it is obvious that "memorandum" greatly reduces the number of subproblems and completely eliminates the redundancy of subproblems, so that the total number of subproblems will not exceed n, that is, the number of subproblems is O(n).The time to deal with a subproblem is still O(k), so the total time complexity is O(kn).