Algorithms and Data Structures (24) Optimal substructure principle and dp array traversal direction

Isn’t dynamic programming derived from the simplest base case? It can be imagined as a chain reaction, from small to big. But only the problem conforming to the optimal substructure has the nature of this chain reaction.

The process of finding the optimal substructure is actually the process of proving the correctness of the state transition equation. If the equation conforms to the optimal substructure, a brute-force solution can be written. By writing a brute-force solution, you can see whether there are overlapping sub-problems. If there are, optimize , if not, then OK. This is also a routine, and readers who often brush questions should be able to understand it.

I won’t give examples of authentic dynamic programming here. Readers can look through historical articles to see how state transitions follow optimal substructures. That’s all for this topic. Let’s look at other confusing behaviors of dynamic programming.

Note:

1. The optimal substructure is only a necessary condition for dynamic programming problems, such as finding the maximum value of a binary tree, but most of the problems that can find the maximum value have the optimal substructure;
2. The dynamic programming problem must be to find the optimal value;
3. The process of finding the optimal substructure is actually the process of proving the correctness of the state transition equation. If the equation conforms to the optimal substructure, a brute-force solution can be written. By writing a brute-force solution, you can see whether there are overlapping sub-problems. If there are, optimize , if not, then OK. This is also a routine, readers who often brush questions should be able to understand;

2. How to see overlapping sub-problems at a glance

Readers often say:

After reading the core routines of dynamic programming in the previous article, I know how to optimize the dynamic programming problem step by step;

After reading the previous article Dynamic Programming Design: Mathematical Induction, I learned to use mathematical induction to write violent solutions (state transition equations).

But even if I write a brute-force solution, it is difficult for me to judge whether this solution has overlapping sub-problems, and thus I cannot determine whether memos and other methods can be used to optimize algorithm efficiency.

Regarding this question, I have actually written several times in the dynamic programming series of articles, so let’s summarize it here.

First of all, the most simple and crude way is to draw a picture, draw the recursive tree, and see if there are any duplicate nodes.

For example, the simplest example, the recursive tree of the Fibonacci sequence in the core routine of dynamic programming:

This recursive tree obviously has duplicate nodes, so we can avoid redundant calculations through memoization.

But after all, the Fibonacci sequence problem is too simple. The actual dynamic programming problem is more complicated, such as two-dimensional or even three-dimensional dynamic programming. Of course, you can also draw a recursive tree, but it is somewhat complicated.

For example, in the Minimum Path Sum Problem, we wrote such a violent solution:

int dp(int[][] grid, int i, int j) {<!-- -->
    if (i == 0 & amp; & amp; j == 0) {<!-- -->
        return grid[0][0];
    }
    if (i < 0 || j < 0) {<!-- -->
        return Integer.MAX_VALUE;
    }

    return Math.min(
            dp(grid, i - 1, j),
            dp(grid, i, j - 1)
        ) + grid[i][j];
}

You don’t need to read the previous article, you can see just by looking at the code of this function that the parameters i, j are constantly changing during the recursive process of the function, that is, the “state” is (i, j) , can you determine whether this solution has overlapping sub-problems?

Assuming the input i = 8, j = 7, the recursion tree of the two-dimensional state is as shown below. Obviously, there is an overlapping sub-problem:

But after a little thought, you will know that there is no need to draw a picture at all. You can directly determine whether there are overlapping sub-problems through the recursive framework.

The specific operation is to directly delete the code details and abstract the recursive framework of the solution:

int dp(int[][] grid, int i, int j) {<!-- -->
    dp(grid, i - 1, j), // #1
    dp(grid, i, j - 1) // #2
}

You can see that the value of i, j is constantly decreasing, so let me ask you a question: If I want to move from state (i, j) to ( i-1, j-1), how many paths are there?

Obviously there are two paths, which can be (i, j) -> #1 -> #2 or (i, j) -> #2 -> #1, There is more than one, indicating that (i-1, j-1) will be calculated multiple times, so there must be overlapping sub-problems.

Let’s take another slightly more complicated example, the brute force solution code for the regular expression problem below:

bool dp(string & amp; s, int i, string & amp; p, int j) {<!-- -->
    int m = s.size(), n = p.size();
    if (j == n) return i == m;
    if (i == m) {<!-- -->
        if ((n - j) % 2 == 1) return false;
        for (; j + 1 < n; j + = 2) {<!-- -->
            if (p[j + 1] != '*') return false;
        }
        return true;
    }

    if (s[i] == p[j] || p[j] == '.') {<!-- -->
        if (j < n - 1 & amp; & amp; p[j + 1] == '*') {<!-- -->
            return dp(s, i, p, j + 2)
               || dp(s, i + 1, p, j);
        } else {<!-- -->
            return dp(s, i + 1, p, j + 1);
        }
    } else if (j < n - 1 & amp; & amp; p[j + 1] == '*') {<!-- -->
        return dp(s, i, p, j + 2);
    }
    return false;
}

The code is a bit complicated, right? It would be a bit troublesome to draw a picture, but we don’t draw a picture, just ignore all the detailed code and conditional branches, and only abstract the recursive framework:

bool dp(string & amp; s, int i, string & amp; p, int j) {<!-- -->
    dp(s, i, p, j + 2); // #1
    dp(s, i + 1, p, j); // #2
    dp(s, i + 1, p, j + 1); // #3
}

Like the previous question, the “state” of this solution is also the value of (i, j), so let me continue to ask you the question: If I want to get from the state (i, j) How many paths are there to transfer code> to (i + 2, j + 2)?

Obviously, there are at least two paths: (i, j) -> #1 -> #2 -> #2 and (i, j) -> #3 -> #3, which shows that this solution has a huge number of overlapping sub-problems.

Therefore, you don’t need to draw a picture to know that this solution also has overlapping sub-problems, which need to be optimized using memo techniques.

Note: Overlapping sub-problems: The stupidest way is to brainstorm a recursion tree to see if there are overlapping sub-problems; further, you can use the recursive framework to determine whether there are sub-problems. If there are sub-problems, you can consider using the memo technique to optimize;

3. Size setting of dp array

For example, regarding the edit distance problem in the following article, I will first talk about the top-down recursive solution, which implements such a dp function:

int minDistance(String s1, String s2) {<!-- -->
    int m = s1. length(), n = s2. length();
    //According to the definition of dp function, calculate the minimum edit distance between s1 and s2
    return dp(s1, m - 1, s2, n - 1);
}

// Definition: The minimum edit distance between s1[0..i] and s2[0..j] is dp(s1, i, s2, j)
int dp(String s1, int i, String s2, int j) {<!-- -->
    // handle base case
    if (i == -1) {<!-- -->
        return j + 1;
    }
    if (j == -1) {<!-- -->
        return i + 1;
    }

    //Perform state transfer
    if (s1.charAt(i) == s2.charAt(j)) {<!-- -->
        return dp(s1, i - 1, s2, j - 1);
    } else {<!-- -->
        return min(
            dp(s1, i, s2, j - 1) + 1,
            dp(s1, i - 1, s2, j) + 1,
            dp(s1, i - 1, s2, j - 1) + 1
        );
    }
}

Then transformed into a bottom-up iterative solution:

int minDistance(String s1, String s2) {<!-- -->
    int m = s1. length(), n = s2. length();
    // Definition: The minimum edit distance between s1[0..i] and s2[0..j] is dp[i + 1][j + 1]
    int[][] dp = new int[m + 1][n + 1];
    //Initialize base case
    for (int i = 1; i <= m; i ++ )
        dp[i][0] = i;
    for (int j = 1; j <= n; j ++ )
        dp[0][j] = j;
    
    // Solve from the bottom up
    for (int i = 1; i <= m; i ++ ) {<!-- -->
        for (int j = 1; j <= n; j ++ ) {<!-- -->
            //Perform state transfer
            if (s1.charAt(i-1) == s2.charAt(j-1)) {<!-- -->
                dp[i][j] = dp[i - 1][j - 1];
            } else {<!-- -->
                dp[i][j] = min(
                    dp[i - 1][j] + 1,
                    dp[i][j - 1] + 1,
                    dp[i - 1][j - 1] + 1
                );
            }
        }
    }
    // According to the definition of dp array, store the minimum edit distance between s1 and s2
    return dp[m][n];
}

The ideas of these two solutions are exactly the same, but some readers asked why the initial size of the dp array in the iterative solution should be set to int[m + 1][n + 1]? Why are the minimum edit distances of s1[0..i] and s2[0..j] stored in dp[i + 1][j + 1 ], is there an index offset?

Can you imitate the definition of the dp function, initialize the dp array to int[m][n], and then let s1[0 ..i] and the minimum edit distance of s2[0..j] should be stored in dp[i][j]?

Theoretically, you can define it however you want, as long as you handle the base case according to the definition.

Look at the definition of dp function, dp(s1, i, s2, j) calculates s1[0..i] and s2[0..j] edit distance, then i, j equal to -1 represents the base case of an empty string, so these two special cases are handled at the beginning of the function.

Looking at the dp array, you can of course define dp[i][j] to store s1[0..i] and The edit distance of s2[0..j], but the question is what to do with the base case? How can the index be -1?

So we initialize the dp array to int[m + 1][n + 1], shift the index by one bit as a whole, and leave index 0 as the base case representation empty string, then define dp[i + 1][j + 1] to store s1[0..i] and s2[0..j] edit distance.

Note: How to define the size of the dp array depends on the base case. For example, in the edit distance problem, the base case dp[0][0] represents an empty string, so the dp array needs to be set to dp[m + 1][n + 1], leave the index 0 to indicate the base case empty string, when doing the question, you can consider the situation of the empty string and then consider setting the size of the dp array;

Fourth, the traversal direction of the dp array

I believe that readers will definitely have some headaches about the traversal order of the dp array when doing dynamic rule problems. Let’s take the two-dimensional dp array as an example, sometimes we traverse forward:

int[][] dp = new int[m][n];
for (int i = 0; i < m; i ++ )
    for (int j = 0; j < n; j ++ )
        // Calculate dp[i][j]

Sometimes we iterate in reverse:

for (int i = m - 1; i >= 0; i--)
    for (int j = n - 1; j >= 0; j--)
        // Calculate dp[i][j]

Sometimes it is possible to traverse diagonally:

// traverse the array obliquely
for (int l = 2; l <= n; l ++ ) {<!-- -->
    for (int i = 0; i <= n - l; i ++ ) {<!-- -->
        int j = l + i - 1;
        // calculate dp[i][j]
    }
}

What is even more confusing is that sometimes it is found that both forward and reverse traversal can get the correct answer.

If you observe carefully, you can find the reason. You just need to hold on to two points:

1. During the traversal process, the required state must have been calculated.

2. After the traversal, the location where the result is stored must have been calculated.

Note:

1. At the beginning of the traversal, the required state must have been calculated;

2. At the end of the traversal, the location where the result is stored must have been calculated;

Let’s explain in detail what the above two principles mean.

For example, the classic problem of edit distance, for detailed explanation, please refer to the detailed explanation of edit distance in the following text. Through the definition of dp array, we have determined that the base case is dp[..][0] and dp[0][..], the final answer is dp[m][n]; and we know dp[i] through the state transition equation [j] needs to be obtained from dp[i-1][j], dp[i][j-1], dp[i- 1][j-1] is transferred, as shown below:

So, with reference to the two principles just mentioned, how should you traverse the dp array? Definitely forward traversal:

for (int i = 1; i < m; i ++ )
    for (int j = 1; j < n; j ++ )
        // pass dp[i-1][j], dp[i][j - 1], dp[i-1][j-1]
        // calculate dp[i][j]

Because, in this way, the left, upper, and upper left positions of each step of iteration are all base cases or have been calculated before, and finally end up in the answer we want dp[m][n].

To give another example, the problem of palindrome subsequence, please refer to the subsequence problem template in the following text for details. Through the definition of dp array, we have determined the diagonal line in the middle of the base case, dp[ i][j] needs to be obtained from dp[i + 1][j], dp[i][j-1], dp[ i + 1][j-1] was transferred, and the final answer I want to ask for is dp[0][n-1], as shown below:

In this case, according to the two principles just mentioned, there are two correct traversal methods:

Either traverse obliquely from left to right, or traverse from bottom to top from left to right, so as to ensure that the left, bottom, and bottom left sides of dp[i][j] have been calculated each time, and we get correct result.

Now, you should understand these two principles. The main thing is to look at the base case and the storage location of the final result. It is enough to ensure that the data used in the traversal process is all calculated. Sometimes there are indeed multiple ways to get the correct answer. Choose according to personal taste.

Note: The essential principle of the dp traversal direction is to use the known to push the unknown, and at the same time, it is necessary to ensure that when the traversal ends, the location of the stored result must have been calculated;

V. References

1. Optimal substructure principle and dp array traversal directions