preface

Recently, I have been reading the algorithm problems related to dynamic programming intermittently. I always feel that dynamic programming needs to be carefully considered. Only by writing and drawing in a book can I calculate boundary conditions and state transition equations, and the most difficult one is the state transition equation. So the core of this paper today is the basic state transition equation and the optimization of state transition equation.

Introduction to Dynamic programming

Dynamic programming is to transform the multi-stage process into a series of single-stage problems, and solve them one by one by using the relations between the stages. At the same time, dynamic programming is a bottom-up solution, which is solved gradually from the most basic known answer to the desired answer through the cycle.

The opening

I think when most people learn dynamic programming for the first time, the first problem must be the basic Fibonacci sequence, and the Fibonacci sequence has many versions of the solution, such as recursion, array and dynamic optimization.

recursive

public int Fibonacci(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return Fibonacci(n-1) + Fibonacci(n-2);
}
Copy the code

Dynamic programming

// Dynamic programming -> The result of this calculation is the sum of the first two
public int Fibonacci(int n) {
    int[] arrs = new int[40];
    arrs[0] = 0;
    arrs[1] = 1;
    for (int i = 2; i <= n; i++) {
        arrs[i] = arrs[i-1] + arrs[i-2];
    }
    return arrs[n];
}
Copy the code

Dynamic programming optimization

/** * Dynamic programming optimization * Time complexity: O(n) * space complexity: O(1) */
public int Fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    int one = 0;
    int two = 1; // Store only the last two digits n(two)/n-1(one)
    for (int i = 2; i < n; i++) {
        int temp = two;
        two = one + two;
        one = temp;
    }
    return two+one;
}
Copy the code

In dynamic programming optimization, we can reduce the original spatial complexity from O(n) to O(1) by saving only the values required for each solution.

sublimation

Now on the basis of the previous increase in difficulty, now there is a question the longest common substring, the specific question does not say, directly on the answer.

/ dynamic equation of state of * * * * : dp. [I] [j] = s1 chatAt (I) = = s2. The charAt (j) && dp [I - 1] [1] : * time complexity O (m * n) * space complexity: O (m * n) * /
public String LCS (String str1, String str2) {
    int[][] dp = new int[str1.length()+1][str2.length()+1];
    int max = 0; // Maximum length
    int position = 0; / / coordinates
    
    for (int i = 1; i < str1.length()+1; i++) {
        for (int j = 1; j < str2.length()+1; j++) {
            if (str1.charAt(i-1) == str2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
                if(dp[i][j] > max) { max = dp[i][j]; position = j; }}}}return max == 0 ? "1" : str2.substring(position-max, position);
}
Copy the code

Dynamic programming optimization

/ dynamic equation of state of * * * * : dp [I % 2] [j]. = s1 chatAt (I) = = s2. The charAt (j) && dp [I % 2 = = 0. 1: 0][J-1] * Time complexity: O(m*n) * Space complexity: O(m*2) */
public String LCS (String str1, String str2) {
    // write code here
    int l = str1.length() > str2.length() ? str1.length() : str2.length();
    int[][] dp = new int[2][l+1];
    int max = 0; // Maximum length
    int position = 0; / / coordinates
    
    for (int i = 1; i < str1.length()+1; i++) {
        for (int j = 1; j < str2.length()+1; j++) {
            if (str1.charAt(i-1) == str2.charAt(j-1)) {
                // Get the value of the node at the previous level
                dp[i%2][j] = dp[i%2= =0 ? 1 : 0][j-1] + 1;
                if (dp[i%2][j] > max) {
                    max = dp[i%2][j]; position = j; }}else {
                dp[i%2][j] = 0; / / not equal}}}return max == 0 ? "1" : str2.substring(position-max, position);
}
Copy the code

In this version of optimization, the value of the current node is only related to the value of the node in the previous layer by virtue of previous usage characteristics. Therefore, the final optimization is to store the data of this row and the data of the previous row, so that only the data of the previous layer can be obtained in the calculation of DP [I][j].

conclusion

You can focus on just one problem, but when you’re done, you need to focus on the big picture so that you can gain more knowledge.

Personal note

The contents of this blog are all notes made by the author to learn, invade and delete! If used for other purposes, please specify the source!