Dynamic programming design: longest increasing subsequence

After reading this article, you can try to solve the following questions:

509. Fibonacci numbers

322. Change

———–

This article is an advanced version of our famous work “Detailed Dynamic Programming”, which was praised by more than 200 people half a year ago. Due to account migration, the old article could not be found, so I polished it up and added more dry goods, hoping that this article would be part of the “guidelines” for solving dynamic planning.

Dynamic Programming problems should be a headache for many readers, but they are also among the most tricky and interesting. An entire chapter is devoted to this algorithm, and the importance of dynamic programming is evident.

If you brush more questions, you will find that the algorithm skills are just a few routines. In our subsequent chapters on dynamic planning, we are using the framework thinking of solving problems in this paper. If you know it, it will be much easier. Therefore, in the first chapter of this paper, to pull down the pants of dynamic programming, to form a set of thinking framework to solve this kind of problems, hoping to become a guideline to solve the problem of dynamic programming. This article will explain the basic routine framework of the algorithm, the following dry goods.

First of all, the general form of dynamic programming problem is to find the best value. Dynamic programming is actually an optimization method in operations research, but it is more used in computer problems, such as the longest increasing subsequence, the smallest editing distance and so on.

So what’s the core problem? The core problem of dynamic programming is exhaustion. Because to get the best possible answer, you have to run out all the possible answers and look for the best possible answer.

Dynamic programming is so simple, you can just do it all, right? All the dynamic programming problems I see are hard!

First of all, dynamic programming exhaustion is a little special, because such problems have “overlapping sub-problems”, and the efficiency will be extremely low if violent exhaustion occurs. Therefore, “memo” or “DP table” is needed to optimize the process of exhaustion and avoid unnecessary calculation.

Moreover, the dynamic programming problem must have the optimal substructure, so that the optimal value of the original problem can be reached through the optimal value of the subproblem.

In addition, although the core idea of dynamic programming is to exhaust the optimal value, but the problem can be infinitely variable, exhaust all feasible solutions is not easy, only list the correct “state transition equation” ** can correctly exhaust.

The overlapping subproblem, optimal substructure and state transition equation mentioned above are the three elements of dynamic programming. The specific meaning will be explained in detail later, but in actual algorithm problems, writing state transition equation is the most difficult, which is why many friends think dynamic programming problem is difficult, I will provide a thinking framework developed by me to help you think about state transition equation:

Base case -> State -> Select -> define dp array/function meaning.

Follow the above routine, the final result can be set within this framework:

Initialize base case
dp[0] [0] [...].  = basePerform a state transition
forstate1 instate1All values of:forstate2 instate2All values of:for. Dp [state1] [state2] [...]. = evaluate (select1, the choice of2...)
Copy the code

The Fibonacci sequence problem and the change problem are used to explain the basic principles of dynamic programming. The former mainly gives you an idea of what an overlap subproblem is (the Fibonacci sequence is not optimized, so it is not strictly a dynamic programming problem), while the latter mainly focuses on how to write state transition equations.

PS: I have carefully written more than 100 original articles and brushed 200 force button topics hand by hand, all of which were published in labuladong’s algorithm cheat sheet and updated continuously. Suggested collection, in accordance with the order of my article brush topic, master all kinds of algorithm set to re-enter the sea of questions like a duck in water.

Fibonacci sequence

Please don’t be annoyed by the simplicity of this example, which allows you to focus on the general ideas and techniques behind the algorithm without getting bogged down in obscure details. History is full of difficult examples.

1. Violence recursion

The mathematical form of the Fibonacci sequence is recursive, written in code like this:

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}
Copy the code

I don’t need to talk about this, because it’s the kind of thing that school teachers use when they talk about recursion. We also know that while it’s easy to write code like this, it’s inefficient. What’s inefficient about it? Assuming n = 20, draw the recursion tree:

PS: Whenever you encounter problems that require recursion, it is best to draw recursion trees, which will help you analyze the complexity of the algorithm and find the reasons for the inefficiency of the algorithm.

How do I understand this recursion tree? So if I want to solve f of 20, I have to solve f of 19 and F of 18, and then to solve f of 19, I have to solve f of 18 and F of 17, and so on. And then when you finally get to f(1) or f(2), you know the answer, you can just return the answer, and the recursion tree doesn’t grow down anymore.

How do I calculate the time complexity of the recursive algorithm? It’s the number of subproblems times the time it takes to solve a subproblem.

First, calculate the number of subproblems, that is, the total number of nodes in the recursive tree. Obviously, the total number of nodes in the binary tree is exponential, so the number of subproblems is O(2^n).

Then calculate the time to solve a subproblem, in this algorithm, there is no loop, only an addition operation f(n-1) + f(n-2), time O(1).

So, the time complexity of this algorithm is O(2^n), exponential, explosion.

Looking at the recursion tree, it is obvious why the algorithm is inefficient: there are a lot of repeated computations, for example, f(18) has been calculated twice, and you can see that the recursion tree with f(18) as the root is huge, so it will take a lot of time to calculate it more than once. Moreover, not only the node f(18) is repeatedly calculated, so this algorithm is extremely inefficient.

This is the first property of dynamic programming problems: overlapping subproblems. Now, let’s try to solve this problem.

2. Recursive solution with memo

Identify the problem, in fact, has already solved the problem half. The reason why it is time-consuming is repeated calculation, so we can build a “memo”, each time after calculating the answer to a sub-question, do not rush back, first write down in the “memo” and then return; Every time you encounter a subproblem, look it up in the “memo” section. If you find that the problem has been solved before, just take the answer out and use it instead of taking time to calculate it.

You usually use an array to act as the “memo”, but you can also use a hash table (dictionary), the idea is the same.

int fib(int N) {
    if (N < 1) return 0;
    // All memos are initialized to 0
    vector<int> memo(N + 1.0);
    // perform recursion with memo
    return helper(memo, N);
}
 
int helper(vector<int>& memo, int n) {
    // base case 
    if (n == 1 || n == 2) return 1;
    // It has been calculated
    if(memo[n] ! =0) return memo[n];
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}
Copy the code

Now, draw the recursion tree, and you’ll know exactly what memo does.

In fact, the recursion algorithm with “memo” transforms a recursion tree with huge redundancy into a recursion graph without redundancy through “pruning”, which greatly reduces the number of sub-problems (i.e. nodes in the recursion graph).

How do I calculate the time complexity of the recursive algorithm? It’s the number of subproblems times the time it takes to solve a subproblem.

The number of subproblems is the total number of nodes in the graph. Since there is no redundant calculation in this algorithm, the subproblems are F (1), F (2), F (3)… F (20), the number is proportional to the input size n = 20, so the number of subproblems is O(n).

The time to solve a subproblem, same as above, with no loops, is O(1).

Therefore, the time complexity of this algorithm is O(n). Rather than brute force, it’s dimension reduction.

At this point, recursive solutions with memos are as efficient as iterative dynamic programming solutions. In fact, this solution is pretty much the same as iterative dynamic programming, except it’s called “top down” and dynamic programming is called “bottom up.”

What do you mean “top down”? Notice the recursion tree, or the graph, that we just drew, goes from top to bottom, from a big original problem like F (20), and then scales down, all the way to the base cases of F (1) and F (2), and then returns the answer layer by layer, which is called “top down.”

What do you mean “bottom up”? Instead, we go straight from the bottom, the simplest, smallest problem, f(1) and F (2), and work our way up until we get to the answer we want, F (20). That’s the idea of dynamic programming, and that’s why dynamic programming usually gets rid of recursion, and it’s done iteratively.

3. Iterative solution of DP array

Inspired by the “memo” in the previous step, we can separate this “memo” into a table, called DP Table, and complete the “bottom-up” calculation in this table, isn’t it beautiful!

int fib(int N) {
    vector<int> dp(N + 1.0);
    // base case
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= N; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[N];
}
Copy the code

This is easy to understand by drawing a graph, and you can see that this DP table is very similar to the result of “pruning” before, but in reverse. In fact, the “memo” in the recursive solution with memo is the DP table after the final completion, so the two solutions are almost the same, and the efficiency is basically the same in most cases.

Here, the term “state transition equation” is introduced, which is actually a mathematical form describing the structure of the problem:

Why is it called “state transition equation”? It’s just to sound high-end. You take f(n) and you want to do a state N, and the state N is transferred by adding states N minus one and states N minus two, and that’s called a state transition, and that’s it.

You will notice that all of the operations in the above solutions, such as return f(n-1) + f(n-2), dp[I] = dp[i-1] + dp[i-2], and initialization of memos or DP tables, are around different representations of this equation. It is important to list “state transition equation”, which is the core of solving the problem. And it’s easy to see that the transition equation directly represents the violent solution.

Don’t look down on the violent solution, the most difficult thing about dynamic programming problems is to write the violent solution, the state transition equation. As long as the violent solution is written, the optimization method is no more than a memo or DP table, there is no magic.

At the end of this example, we’ll talk about detail optimization. Careful readers will find that according to the Fibonacci sequence of state transition equation, the current state is only related to the previous two states, in fact, there is no need for such a long DP table to store all states, just find a way to store the previous two states on the line. Therefore, further optimization can be made to reduce the spatial complexity to O(1) :

int fib(int n) {
    if (n == 2 || n == 1) 
        return 1;
    int prev = 1, curr = 1;
    for (int i = 3; i <= n; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}
Copy the code

This technique is known as “state compression”. If we find that only part of the DP table is needed for each state transition, we can try using state compression to reduce the size of the DP table, recording only the necessary data. The above example is equivalent to reducing the size of the DP table from N to 2. We will see an example of this later in the chapter of dynamic programming. Generally speaking, a two-dimensional DP table is compressed into one dimension, that is, the space complexity is compressed from O(n^2) to O(n).

One may ask why optimal substructures, another important feature of dynamic programming, are not covered. This will be covered below. The Fibonacci sequence example is not strictly a dynamic programming, because there is no optimization involved. The above purpose is to illustrate the elimination method of overlapping subproblems and demonstrate the process of progressively refining the optimal solution. Now, let’s look at the second example, the change problem.

Second, the change problem

Let’s take a look at the title: here you are given coins of K denominations, c1, C2… Ck, there is an infinite number of each coin, give an amount, and ask how many coins you need to make up the amount. If that is not possible, the algorithm returns -1. The functional signature of the algorithm is as follows:

// Coins is an optional coin value, and amount is the target amount
int coinChange(int[] coins, int amount);
Copy the code

For example, k = 3, denominations 1,2,5, and total amount = 11. So you need at least 3 coins, 11 = 5 + 5 + 1.

How do you think computers should solve this problem? Obviously, just list all the possible ways to make up coins, and find the minimum number of coins you need.

1. Violence recursion

First, this problem is a dynamic programming problem because it has “optimal substructure”. To conform to “optimal substructure”, subproblems must be independent of each other. What do you mean independent? You don’t want to see a mathematical proof, but let me just do an intuitive example.

For example, if you take an exam, each subject is independent of the other. Your original problem is to get the highest total score, so your sub-problem is to get the highest Chinese test, the highest math test…… In order to get the highest score for each subject, you need to get the highest multiple-choice score for each subject, the highest cloth-fill score for each subject… Of course, the ultimate result is that you get full marks in every subject, which is the highest overall grade.

The correct result is obtained: the highest total score is the total score. Because this process is in line with the optimal sub-structure, “get the highest test in each subject” these sub-problems are independent of each other.

However, if you add a condition: your Chinese score and math score will be mutually restricted, high math score, Chinese score will decrease, and vice versa. In this case, obviously the highest total score you can get is not the total score, according to the previous thinking will get the wrong result. Because subproblems are not independent, Chinese and mathematics scores cannot be optimized at the same time, so the optimal substructure is destroyed.

Back to the change problem, why is it optimal substructure? For example, if you want to find the minimum number of coins when amount = 11 (original problem), if you know how to get to the minimum number of coins when amount = 10 (subproblem), you simply add one to the answer to the subproblem (and pick a coin of value 1) to get the original problem. Since there is no limit to the number of coins, the subproblems are independent of each other.

PS: We will discuss the optimal substructure with examples in the q&A on dynamic programming.

So, now that we know this is a dynamic programming problem, we have to think about how do we write the correct state transition equation?

If amount is 0, the algorithm returns 0 because it doesn’t need any coins to get the target amount.

2. Determine the “state”, that is, the variables that change in the original problem and its subproblems. Since there are an infinite number of coins and the denomination of the coins is given by the question, only the target amount is constantly approaching the base case, so the only “state” is the target amount.

3. Identify “choices”, that is, actions that lead to changes in “states”. Why does the target amount change? Because you’re choosing coins, and every coin you choose, you’re reducing the target amount. So the face value of all the coins is your “choice.”

4. Define dp functions/arrays. We’re talking about a top-down solution here, so we have a recursive dp function, and generally the parameter of the function is the amount of change in the state transition, the “state” mentioned above; The return value of the function is what they’re asking us to evaluate. In this case, there is only one state, the “target amount”, and they ask us to calculate the minimum number of coins needed to make up the target amount. So we can define the dp function like this:

Definition of dp(n) : Enter a target sum n and return the minimum number of coins that make up the target sum n.

The pseudocode of the solution can be written by making clear the above key points:

# pseudo-code framework
def coinChange(coins: List[int], amount: int) :

    To raise the sum n, at least DP (n) coins are required
    def dp(n) :
        # Choose the result that requires the fewest coins
        for coin in coins:
            res = min(res, 1 + dp(n - coin))
        return res

    # the end result is dp(amount)
    return dp(amount)
Copy the code

According to the pseudo-code, we add the base case to get the final answer. Obviously, if the target amount is 0, the number of coins required is 0; When the target amount is less than 0, there is no solution and -1 is returned:

def coinChange(coins: List[int], amount: int) :

    def dp(n) :
        # base case
        if n == 0: return 0
        if n < 0: return -1
        # minimizes, so initialize to positive infinity
        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coin)
            # No solution to subproblem, skip
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)

        return res ifres ! =float('INF') else -1
    
    return dp(amount)
Copy the code

At this point, the state transition equation is actually complete, the above algorithm is already a violent solution, the above code mathematical form is the state transition equation:

If amount = 11, coins = {1,2,5}, draw the recursion tree:

Time complexity analysis of recursive algorithms: total number of subproblems x time of each subproblem.

The total number of subproblems is the number of nodes in the recursion tree, which is hard to see, order n to the k, but it’s exponential. Each subproblem contains a for loop of O(k) complexity. So the total time is O(k * n^k), exponential.

2. Recursion with memo

Similar to the previous Fibonacci sequence example, with minor modifications, the sub-problem can be eliminated via the memo:

def coinChange(coins: List[int], amount: int) :
    # memo
    memo = dict(a)def dp(n) :
        Check memos to avoid double counting
        if n in memo: return memo[n]
        # base case
        if n == 0: return 0
        if n < 0: return -1
        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coin)
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)
        
        # Memo entry
        memo[n] = res ifres ! =float('INF') else -1
        return memo[n]
    
    return dp(amount)
Copy the code

It is obvious that “Memorandum” greatly reduces the number of subproblems and completely eliminates the redundancy of subproblems, so the total number of subproblems cannot exceed the amount 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).

3. Iterative solution of DP array

Of course, we can also use dp table from bottom to top to eliminate overlapping subproblems. There is no difference in “state”, “selection” and base case. The definition of DP array is similar to the dp function just before, and also takes “state”, i.e. target amount, as a variable. But dp functions are represented in function arguments, and dp arrays are represented in array indexes:

Definition of dp array: when the target amount is I, at least DP [I] coins are needed.

According to the dynamic programming code framework given at the beginning of the article, the following solution can be written:

int coinChange(vector<int>& coins, int amount) {
    // The array size is amount + 1 and the initial value is amount + 1
    vector<int> dp(amount + 1, amount + 1);
    // base case
    dp[0] = 0;
    // The outer for loop iterates through all values in all states
    for (int i = 0; i < dp.size(a); i++) {// The inner for loop minimizes all selections
        for (int coin : coins) {
            // Subproblem no solution, skip
            if (i - coin < 0) continue;
            dp[i] = min(dp[i], 1+ dp[i - coin]); }}return (dp[amount] == amount + 1)?- 1 : dp[amount];
}
Copy the code

The dp array is initialized to amount + 1 because the number of coins that make up the amount can only be as high as the amount (all 1-dollar coins), so initializing the amount + 1 equals infinity.

Third, the final conclusion

The first Fibonacci sequence problem explains how to optimize a recursion tree using a “memo” or “DP table” method, and makes it clear that the two methods are essentially the same, just different from top-down.

The second change question shows how processes can be streamlined to determine the “state transition equation”. As long as violent recursive solutions are written through the state transition equation, all that remains is to optimize the recursion tree and eliminate overlapping subproblems.

If you don’t know much about dynamic programming, and you’re looking at this, I give you a big hand, you’ve got the design skills of this algorithm.

There is no clever way for a computer to solve a problem. Its only solution is to exhaust all possibilities. Algorithmic design is all about thinking about how to do it first, and then pursuing how to do it intelligently.

To list the dynamic transfer equation is to solve the problem of “how to exhaust”. The reason why it is difficult is that many of the problems require recursive implementation, and the other reason is that the solution space of some problems is so complex that it is not easy to complete them.

Memos and DP tables are all about “how to be smart.” The idea of using space for time is the only way to reduce the complexity of time. In addition, we ask, what can we play?

Later we will have a chapter devoted to dynamic programming. If you have any questions, please feel free to reread this article. We hope that readers can rely more on “states” and “choices” when reading each topic and solution so that they can develop their own understanding of this framework and use it freely.

＿＿＿＿＿＿＿＿＿＿＿＿＿

My online e-book has 100 original articles, hand handle with brush 200 force buckle topic, suggest collection! The corresponding GitHub algorithm repository has been awarded 70K Star, welcome standard star!

Dynamic programming design: longest increasing subsequence

Fibonacci sequence

Second, the change problem

Third, the final conclusion

Related Posts

Ubuntu MySQL 5.7 turns off strict mode

Cloud mi Dubbo3.0 practice: moving from microservices to cloud to traffic governance

Rctf2015-mobile – Writeup