What is the

Dynamic programming is not an algorithm, but an algorithm idea. The complex problem is divided into subproblems and then the solution of the original problem is obtained by solving the subproblems.

Given a problem, we solve its different parts (i.e., the subproblem), and then solve the original problem according to the solution of the subproblem. The feasibility of using algorithm to solve problems requires the relationship between subproblems and original problems as well as the relationship between subproblems, that is, optimal substructure and repeated subproblems

Optimal substructure

Optimal substructure is the relationship between subproblems and original problems.

Dynamic programming is the optimal solution of some problems. By disassembling the original problem into sub-problems of different parts, and then recursively looking for the optimal solution of each sub-problem, and finally through certain mathematical methods to combine the optimal solution of the sub-problem to get the final solution.

The final solution of the original problem can be obtained by combining the solutions of the sub-problems, which is the key to the feasibility of dynamic programming. In general, this combination is described by state transition equation. For example, the solution of the original problem is F (n), where F (n) is also called the state. The state transition equation F (n) = F (n-1) + F (n-2) describes the combinatorial relationship between the subproblem and the original problem. Meanwhile, in the process of solving the original problem, different choices may correspond to different combination relations between subproblems (n= 2K and n= 2K +1 here represent different choices, corresponding to different combinations of subproblems) :

F (n−1)+f(n−2) n=2k F (n)={f(n−1) n=2k+1Copy the code

If the optimal substructure is found, a state transition equation can be derived, and the recursive implementation of the problem can be quickly obtained by the state transition equation.

Repeating subproblem

Repetitive subproblems refer to the relationship between subproblems. When we recursively search for the optimal solution of a subproblem, we repeatedly encounter smaller problems. These problems lead to double computation, and dynamic programming guarantees that each repeating subproblem will be computed only once. When recomputing problems are solved, memorization recursion is generally adopted: if the range of sub-problems can be determined in advance, tables can be built to store the answers of sub-problems.

To solve the core of dynamic programming: to find the relationship between subproblems and original problems

Key points of understanding optimal substructures and repeating subproblems in dynamic programming algorithms:

  • The solution to proving the problem involves an option that leaves one or more subproblems
  • Design the combinatorial relation between subproblems, namely state state transition equation
  • Prove that subproblems overlap and are stored by memorization

How to do

Example: description: given an unordered array, find the ascending subsequence with the largest length example: input: [10,9,2,5,3,7,101,18] output: 4 explanation: the longest ascending subsequence is [2,3,7,101], which has length 4.Copy the code

Whether the problem scale can be reduced or not, some typical reduction methods are the basis of dynamic programming classification. Linear, interval, tree, etc. There are two common ways to consider arrays:

- each time cut in half: tall problem,9,2,5 [10] and [3,7,101,18] [2, 5) is the most optimal solution and,7,101 [3]. The optimal solution of these two sub-problems cannot be obtained by some combination of the optimal solution of the original problem [2,3,7,101] - one reduction at a time: remember f[n] as the sequence ending in the NTH element, one reduction at a time, decompose the original problem into F [n-1], F [n-2]... F [1] n-1 problems. N-1 = 7 questions are answered as follows: [10, 9, 2, 5, 3, 7, 101] - > [2, 5, 7, 101] [10, 9, 2, 5, 3, 7] - > [2, 5, 7] [10, 9, 2, 5, 3] - > [2, 3] [10, 9, 2, 5] -> [2, 5] [10, 9, 2] -> [2] [10, 9] -> [9] [10] -> [10] The optimal solution of the original problem can be obtained through a combination method. The result of F [6] [2, 5, 7], 7 < 18, and the length is the longest among the results of f[1]~ F [7] whose ending element is less than 18. The length of F [7] is 4. Although the length is the longest, the ending element 101 is greater than 18, which cannot be combined into the solution of the original problem. The above combination can be summarized into a state transition equation: f[n]= maxf[I] + 1 where I <n and A [I]<a[n] - Conclusion: The two most difficult points to solve the dynamic programming problem are: - how to define f[n] - how to pass f[1], f[2]... F [n-1] derives F [n], that is, how do you derive the state transition equationCopy the code

  1. recursive

    With the state transition equation, you can actually do it recursively

    func find(arr []int.len int) (res int){
    res := 1
    for i :=0; i<len; i++ {
        if (arr[i] < arr[len]) {
            res = max(res, find(arr , i) + 1)}}return res
}
Copy the code

  2. Top down (mnemonics)

    There will be a lot of repeated calculation in the solving process of the recursive method. The mnemonic method records in solving f[1], F [2]… The results in the process are saved in a table, which can be used directly if the results of the previous subproblems are encountered when solving the subsequent subproblems.

    func find(arr []int.len int, dp []int)(res int) {
    if (dp[len] != - 1) {return dp[len]
    }
    res := 1
    for i :=0; i<len; i++ {
        if (arr[i] < arr[len]) {
            res = max(res, find(arr , i) + 1)
        }
    }
    dp[len] = res
    return res
}
Copy the code

  3. Bottom-up (iterative)

    Due to the existence of the state transition equation, we can approach the scale of the original problem step by step by increasing the scale of the problem. In this process, the solution of each problem needs to be recorded to avoid double-counting