We often come across a question like this:

There are lots of permutations between elements, so let’s pick the best one that satisfies one of these conditions.

Such as:

  • A string can have n substrings, so let’s pick the longest palindrome. (A palindrome string is a string like abccba which in turn is equal to the original string.)

  • There are many combinations of n items, so let’s pick the combination that satisfies the maximum value that is less than a certain value

The easiest way to think about these problems is to enumerate all the cases and then verify and compare them.

For example, the first question:

We can enumerate all the substrings, and then determine if it’s a palindrome, and record the longest one.

Second question:

You can enumerate all combination schemes, verify whether the weight is less than a certain value, and record the scheme with the maximum value that satisfies the condition.

This idea of enumerating all the permutations and combinations, and then verifying and comparing them in turn is the easiest to think of, and many problems are solved in this way.

But the business requirements of doing this for some simple scenarios are ok, if the data size goes up, immediately GG.

Why is that?

The solution to the first problem, to enumerate all substrings, is to enumerate the coordinates of all start and stop coordinates, and then determine whether it is a palindrome string.

This requires a loop of 2 to enumerate substrings and a loop to determine palindrome and compare with the maximum value.

That’s order n^3.

The solution to the second problem is to enumerate all the combinations, each item has a choice or no choice, and recurse n times to calculate all of them, so there are 2 to the n possible combinations, and then calculate the sum of the values of the m items.

That’s order 2 to the n times m.

Can this solution solve a business problem? Yes, in fact, in many cases we use this kind of naive thinking to solve the problem, but when the data scale up, these solutions are broken. The reasons are shown below:

When the data size is relatively large, it is necessary to switch to a lower time complexity algorithm.

How can we reduce the time complexity?

We are now enumerating each one and judging it individually:

Each case has to be done separately, so the more combinations, the more complexity.

Can you find a pattern between the various combinations, like from one situation to another, so you don’t have to check it every time?

For example, the palindrome question, if we know that I and j are palindromes, wouldn’t i-1 to j+1 also be palindromes if the first and second characters are equal?

So the derivation can be found as follows:

if (str[i] === str[j] && isHuiwen[i+1][j-1]) {
    isHuiwen[i][j] = true;
}
Copy the code

So what happens with this derivation? We don’t have to enumerate each case and verify it individually, just deduce all the following cases from one initial case.

You can derive it directly from the result, and all of a sudden you go from order n^3 to order n.

This algorithm of finding patterns between situations, and then deducing all the states from the initial state from the state transition equation is calledDynamic programming.

If the knapsack problem can find the derivation relationship between the results, there is no enumeration + verification, can be directly deduced.

Let’s try to find:

What we care about is what is the maximum value of I items with j available capacity.

So what’s the relationship between item I and item I minus 1? Is to pretend or not to pretend.

If the available capacity J is less than the weight of the ith item W [I], it will not fit.

That is

 if (j < w[i]) {
     maxValue[i][j] = maxValue[i -1][j]
 }
Copy the code

If the available capacity j is greater than or equal to the weight of the ith item w[I], then it fits.

If you can fit it, you can divide it into two cases:

 if (j >= w[i]) {
     maxValue[i][j] = Math.max(maxValue[i][j - w[i]] + val[i], maxValue[i-1][j])
 }
Copy the code

This is the relationship between item I and item I-1:

 if (j < w[i]) {
     maxValue[i][j] = maxValue[i -1][j]
 } else {
     maxValue[i][j] = Math.max(maxValue[i][j - w[i]] + val[i], maxValue[i-1][j])
 }
Copy the code

Once you have this state transition equation, you can derive all the states from the initial state, and then take the maximum value of n items that satisfy the volume w.

The complexity went from O(2^n * m) to O(n * m).

conclusion

When it comes to the problem of choosing the combination that meets the requirements from a variety of combinations, the general idea is enumeration + verification, but this idea has high algorithm complexity and poor performance.

If you can find the derivation relationship between various combinations, it can be directly deduced, such as the relationship between the palindrome string from I to J and the palindrome string from I-1 to J +1, such as the relationship between the maximum value of I items with a capacity of J and the relationship between i-1 items with a capacity of J.

This idea is called a dynamic programming algorithm.

The difficulty of dynamic programming is to find the derivation relation between I and I -1, that is, to list the state transition equation.

Once the state transition equation, which is the derivation between the results of the combinations (states), is understood, all subsequent states can be derived from the initial state. It can greatly reduce the complexity of the naive algorithm and improve the performance of several orders of magnitude.