Article/Cainiao network – Zhenyu

​

Let’s start with the official definition of dynamic programming:

• Dynamic programming is a branch of operations research, and it is a process to solve the optimization of decision process. (by Baidu Baike)
• Dynamic programming algorithm is to solve each subproblem only once, and store its results in a table, so as to avoid recalculating the answer every time each subproblem is encountered. (Introduction to by algorithm)

precondition

• Optimization principle: an optimization strategy has the property that, regardless of the past state and decision, for the state formed by the previous decision, the remaining decisions must constitute the optimal strategy. In short, the substrategies of an optimization strategy are always optimal. A problem satisfying the optimization principle is also said to have the property of optimal substructure (Yuan Pingbo, Gu Weibing, Yin Dong, Ed. Data Structure and Applied Algorithms: University of Science and Technology of China Press, 2013-09)
• No aftereffect: after all stages are arranged in a certain order, for a given stage state, the state of its previous stages cannot directly affect its future decision, but only through the current state. In other words, each state is a complete summary of past history. This is called no backwardness, also known as no aftereffect.

My point of view

The intermediate state of the computation is stored in a DP array to avoid double computation. (Overlap subproblem)

The basic concept

The following is a chestnut 🌰 to introduce the basic concept of dynamic programming: now there are enough 1 yuan, 2 yuan, 5 yuan coins, need to gather N yuan, find the minimum number of coins used. Assuming that n is now 10099, the diagram analysis is as follows:

It can be seen from the figure that DP [10097] has been repeatedly calculated twice, and when the number is smaller, it has been repeatedly calculated more times. If you use a memo array to record, you can avoid double calculation, which is the core of dynamic programming algorithm can improve the efficiency of calculation, space for time. Therefore, we can define a one-dimensional array dp to store the computed intermediate state, where dp(I) represents the minimum number of coins used to make up the i-element. This is the memo. Dp = [f(0), f(1)… f(10097)… Where f(0) is the initial state. From the figure, it can be seen that dp[10099] = min(dp[10098], DP [10097],dp[10094]) + 1 can be deduced: F (n) = math.min (f(n-1)), f(n-2), f(n-5)) + 1 A good summary is dynamic programming DP = recursion plus cache.

The difficulties in

The difficulties of dynamic programming are mainly reflected in the following two aspects:

• How to cache? => DP array dimension, state?
• How do I get recursion? => Solution of state transition equation

In particular, to solve the state transition equation, there is no fixed formula, it can only be obtained from the analysis of the problem.

Dynamic programming takes four steps

Dynamic programming problems can be solved by following four steps:

1. Define cache DP
2. The initial state
3. State transition equation
4. Get the results from the DP cache

​

LeetCode instance

The analysis process

First draw and analyze example 1, as shown below:

Then consider adding a number X after 12. X is special when taking 0, because 0 cannot be transcoded into any letter, but can only be combined with the preceding number, as shown in the figure below.

The 2 before the X is not representative, so consider converting the 2 to the letter P.

When X is equal to 0, there are two situations

• When P is 1 or 2, it can be combined with X is 0 to form 10 or 20.
• When that P is greater than 2, PX definitely can’t be converted to a letter and returns 0.

When X is not equal to 0, there are also two cases:

• If P is 0, X cannot combine with P, and 1PX and 1P have the same result
• P is not equal to 0, which is subdivided into the following two cases:
  1. If PX > 26, PX cannot be converted into letters, but can only be split. In this case, the result of 1PX is the same as the result of 1
  2. When PX is less than or equal to 26, P and X can be transcoded separately. The result of 1PX is the same as that of 1P. Or a combination of PX and transcoding, where 1PX and the result is the same as the result of 1.

The specific analysis process is shown in the figure below:

Apply the four-step method

Step 1: Define the cache DP

Define a one-dimensional number dp, the ith element dp[I] represents the number of decodes from the first character to the ith character.

Step 2: Initial state

If the input is not empty and the first character is not 0, dp[I]=1; otherwise, 0 is returned

Step 3: State transition equation

According to the above analysis chart, the conclusions are as follows:

Step 4: Get the results from the DP cache

The last term of the dp array is the solution to the problem.

The sample code

Var numDecodings = function (s) {// dp[I] const list = s.split(''); if (list.length === 0 || list[0] === '0') { return 0; } const dp = []; dp[0] = 1; for (let i = 1; i < list.length; i++) { const curChar = list[i]; if (curChar === '0') { if (['1', '2'].includes(list[i - 1])) { dp[i] = i >= 2 ? dp[i - 2] : 1; } else { return 0; } } else { if (list[i - 1] === '0') { dp[i] = dp[i - 1]; } else { const number = Number(list[i - 1]) * 10 + Number(list[i]); if (number <= 26) { dp[i] = i >= 2 ? dp[i - 1] + dp[i - 2] : 2; } else { dp[i] = dp[i - 1]; } } } } console.log(dp); return dp.pop(); }Copy the code

​

conclusion

In fact, dynamic programming problems still need some experience accumulation, which is similar to the process of modeling. Experience needs to be accumulated through continuous contact. The following points are summarized:

1. Whether f(n) and F (n-1),… Is there any correlation between f(0)
2. A memo can be defined during traversal to reduce double counting
3. Remember the four steps

Points 1 and 2 are used to quickly judge whether dynamic programming can be used to solve practical problems. The three points are a template to keep in mind for solving dynamic programming problems.