Using an easy way to solve dynamic programming problems

Algo.monster is mainly concerned with the theoretical knowledge of dynamic programming. First of all, you need to solve this question: what kind of problems can dynamic programming solve? As long as the problem meets “recursion + repetition,” we can use dynamic programming to solve the problem. In short, dynamic programming can solve the issues of meeting “a model with three characteristics.”

What is a model with three characteristics from dynamic programming?


A well-established theory called “a model with three characteristics” theory for what kind of problems are suitable for dynamic programming.

A model from dynamic programming

One model theory refers to the model of the problem that dynamic programming is suitable for solving. We can see this model as a “multi-stage decision optimal solution model.” We generally use dynamic programming to solve optimization problems. The problem-solving process requires multiple decision stages, each of which corresponds to a set of states. Then it is necessary to find a group of decision sequences, after which we find it can generate the optimal value of the final desired solution.

Three features from dynamic programming

The “three features” are optimal substructure, no posteriority, and repeated subproblems. These explanations of three concepts are in detail below.

Optimal substructure

Optimal substructure means that the optimal solution of a problem contains the optimal solution of a subproblem. Conversely, the optimal solution of a problem can come out from the optimal solution of a subproblem.

Suppose the optimal substructure corresponds to the dynamic programming problem model defined above. In that case, we can understand that the state of the later stages comes out from the state of the earlier stages.

Posteriority-free

The first meaning is that only the value of the previous stage is the first requirement when deriving the state of the latter stage, not how the state comes out step by step. The second meaning is that once the condition of a stage is determined, the decisions made in subsequent phases will not affect it. Posteriority-free is a very “loose” requirement. As long as they meet the dynamic programming problem model mentioned above, they will fulfill the non-sequitur.

Repeated subproblems

Different decision sequences, when they reach the same stage, may produce repeated states.

Example: a model with three characteristics

Suppose there is an n-by-n matrix w[n][n]. The matrix stores all positive integers. The starting position of the pieces is in the top left corner, and the ending position is in the bottom right corner. Move the pieces from the top left corner to the bottom right corner. You can only move one piece at a time to the right or down. There will be many different paths to take from the top left corner to the bottom right corner. Add up the numbers that each path passes through as the length of the path. What is the length of the shortest path from the top left corner to the bottom right corner?

General idea

First, see if the problem fits a model? To go from (0, 0) to (n-1, n-1), there are 2(n-1) steps, which corresponds to 2(n-1) stages. Each stage has two decisions: go right or go down, and each stage corresponds to a set of states.


We define the states as min_dist(i, j), where i denote rows and j means columns. min_dist expressions have values that represent the shortest path length from (0, 0) to (i, j). Therefore, this problem is a multi-stage decision optimal solution problem, which is consistent with the dynamic programming model.

Meet the three characteristics

If the backtracking algorithm solves the problem, draw a recursive tree at first. From this, we can see that there are duplicate nodes in the recursive tree. The same nodes indicate that there are multiple routes from the top left corner to the corresponding position of the node. It also shows that there is a duplicate subproblem in this problem. If we draw the graph, then we can see that there are many paths from the upper left corner (0, 0) to the following position (3, 3). And for these many paths, what happens next is the same, i.e., it contains the duplicate subproblem.

When going to the position (i, j), we can only move it through the positions (i-1, j), (i, j-1). That is, to compute the state corresponding to the position (i,j), one only needs to care about the state corresponding to the two positions (i-1, j), (i, j-1), and not about the route through which the pieces arrived at these two positions. Moreover, we only allow downward and rightward movements, not backward ones. So the state of the previous phase is sure and not changed by the decisions made in the later stage, so the problem is “posteriority-free.”

Define the minimum path from the starting position (0, 0) to (i, j) as min_dist(i, j). Since it can only move to the right or down, it is only possible to reach (i, j) from either (i, j-1) or (i-1, j). That is, the shortest path to (i, j) either goes through (i, j-1) or through (i-1, j), and the shortest path to (i, j) must contain one of the shortest paths to these two positions. In other words, min_dist(i, j) can be derived from the states min_dist(i, j-1) and min_dist(i-1, j). It means that the problem is consistent with the “optimal substructure.”

Summary


A model: multi-stage decision optimal solution model, multi-stage means that are decomposing the problem into multiple stages to solve, each stage usually has an optimal solution, we can find the optimal solution of each stage through the recursive formula in the next stage of the optimal solution, the optimal solution of each stage, naturally we will also solve the optimal global solution.

Three features

  1. Optimal substructure: The optimal solution for each stage of a model described above is the optimal substructure
  2. no posteriority: the optimal solution of the current stage is only related to the optimal solution of the previous stage. It does not care how we obtained the optimal solution of the last stage and the decision (optimal resolution) of the subsequent stage does not affect the resolution of the previous stage.
  3. Repeated subproblems: If we solve the problem in a top-down manner, there are usually same subproblems, like what we call “recursion + repetition.” At this time, we can use the bottom-up approach to solve the problem

Dynamic programming solution ideas

  1. determine whether recursion is available to solve the problem. If so, go to step 2
  2. analyze whether there is a large number of repeated subproblems in the process of recursion
  3. use memoization to store the solutions of subproblems to avoid a lot of repeated calculations (pruning)
  4. switch to bottom-up recursion, i.e., dynamic programming

Leave a Reply