This is the 10th day of my participation in Gwen Challenge

Dynamic programming

Dynamic Programming (DP) is a process to solve the optimization of decision process. It is widely used in mathematics, management science, computer science, economics, bioinformatics and other fields to solve complex problems by breaking the original problem into relatively simple sub-problems.

Its basic idea is very simple, if we want to solve a given problem, we need to solve its different parts (namely, the sub-problem), and then obtain the solution of the original problem according to the solution of the sub-problem.

In general, many subproblems are very similar. In order to reduce the amount of computation, the dynamic programming method tries to solve each subproblem only once. Once the solution of a stator problem is calculated, it is memorized and stored, so that the next time the solution of the same subproblem can be directly looked up in the table. Therefore, it has the function of natural pruning.

Characteristics of DP topics

Let’s first take a look at what kind of problems might require dynamic programming. In general (but not always), you can consider using dynamic programming (with some probability) if the following features of a problem occur.

Characteristic one: count

They ask: How many ways are there? How many ways are there?

Key words: How much!

Feature 2: Maximum value/minimum value

They ask: What is the maximum of a certain choice? What is the minimum time to complete the task? What is the oldest sequence of an array? The minimum number of operations to achieve the target.

Key words: most!

Feature three: possibility

Is it possible for something to happen? Is it possible to win the game? Is it possible to extract k numbers that satisfy this condition?

Key words: Yes or no!

And in general, if you look at these three problems, you can try to follow the DP solution.

DP’s 6-step problem-solving method

After identifying the characteristics of the problem and determining that DP can be used, you can then prepare to solve the problem step by step.

Here we take a problem as an example to introduce the thinking process and solving steps of solving DP problems in detail. It’s actually not that hard, and I’m sure you’ve all seen it before, but I want you to follow my lead and rethink it.

【 答 案 】 Given coins of different denominations and an amount, write a function to calculate the minimum number of coins needed to make up the amount. If no one coin combination makes up the total, -1 is returned. You can think of an infinite number of each coin.

Enter: Coins = [1, 2, 5], amount = 11

Output: 3

Explanation: 11 yuan can be split into 5 + 5 + 1, which is the minimum number of coins.

【 答 案 】 First, we can see the keyword “least”, so we can try to think of DP. On THE issue of DP, many people have a misconception, which is called misconception 1:

When solving a problem with DP, start by thinking about what to do first!

The reason why you don’t have ideas is often because you take an adaptive approach to the problem. For example, the question asks:

To figure out the “minimum number of steps,” think “How to start from scratch.” You really start to think about how to choose what will “achieve the greatest benefit.”

This is exactly a “set” that the DP question gives you. Thinking like this will easily lead you to fall into the method of violent solution and find no way to optimize. So don’t start thinking from step one. In this case, don’t think, “How do I pick my first coin?”

So where should we start? The answer is: the last step!

1. Last step

In the example of this question, the last step refers to: when exchanging coins, let’s see how the last step reaches amount, assuming that each step always selects a coin.

Take the given input as an example:

coins = [1, 2, 5], amount = 11

The final step can be obtained with the following three options:

Now that you have converted 10 yuan into coins, add another 1 yuan coin to make 11 yuan;

Now that you have converted 9 yuan into coins, add a 2 yuan coin to make 11 yuan;

Now that you’ve changed the coins for 6 dollars, add a 5 dollar coin to make 11 dollars.

Next, you should immediately expand the unknown items from the above three options into subproblems!

Note: If the size of the problem is not reduced by the last step, you have only found the equivalent of the original problem, not the real last step.

2. The problem of child

Given three options, you may be wondering: how did you get [$10, $9, $6]? At this point, don’t try to recursively solve $10, $9, and $6. Instead, express them as three subproblems:

How to use the least coins to make 10 yuan?

How to use the least coins to make 9 yuan?

How to make 6 yuan from the least number of coins?

Our original problem was how to make 11 dollars with the fewest coins.

It is not difficult to find that if f(x) is used to represent how to use the least coins to form x yuan, the original problem and the three sub-problems can be unified by f(x), and the following content can be obtained:

The original problem is expressed as F (11);

The three sub-problems are expressed as F (10), F (9) and F (6) respectively.

Next, we use f(x) to represent the three options in the last step:

F (10) + 11 yuan is f(11);

F (9) + 1 2 is f(11);

F of 6 plus 1 5 yuan is f of 11.

3. Recursive relationships

Recursive relationships, you usually get them by two substitutions.

The final step can be obtained by three options. Which option is the least number of steps? At this point, we can use a min function to get the minimum from these three options.

f(11) = min(f(11-1), f(11-2), f(11-5)) + 1

Next, the first substitution: just replace 11 with a more general value to get a more general recursion:

f(x) = min(f(x-1), f(x-2), f(x-5)) + 1

Of course, here [1, 2, 5] we still use the input example for the second substitution:

f(x) = min(f(x-y), y in coins) + 1

In pseudocode:

f(x) = inf
for y in coins:
    f(x) = min(f(x), f(x-y) + 1)
Copy the code

4. Expression of F (x)

So what we’re going to do is when we write code, how do we express f of x?

Here’s a little trick.

Just think of f of x as a hash function. So f is a HashMap.

For most DP problems, the f function works if you replace it with HashMap. If you encounter a function similar to f(x, y), you need to express f(x, y) in a nested way: Map<Integer x, Map<Integer y, Integer>>.

Sometimes, of course, it’s simpler and more efficient to use arrays as hash functions. To be specific:

If one-dimensional information is to be expressed, f(x) is represented by the one-dimensional array dp[];

For two-dimensional information, f(x, y) is represented by the two-dimensional array dp[][]

That’s why you see a lot of DP arrays in a lot of DP code. But now you know this:

Using the DP [] array is not the core of the dp problem.

Because arrays are just one way of expressing information. Questions are always variable, and sometimes other data structures may be needed to express information such as f(x) and f(x, y). Such as:

What if x and y in f(x) and F (x, y) are not integers? What if it’s a string? What if it’s a structure?

Of course, as far as this problem is concerned, two characteristics can be found:

1) x in f(x) is an integer;

2) The information f(x) wants to express is one-dimensional information.

So, for this problem, we can use a one-dimensional array, as follows:

int[] dp = new int[amount + 1];
Copy the code

The array subscript I represents x, and the value dp[I] represents f(x).

Then the recursion relation can be expressed as follows:

dp[x] = inf;
for y in coins:
  dp[x] = min(dp[x], dp[x-y] + 1);
Copy the code

5. Initial conditions and boundaries

So, how do you get the initial conditions and the boundary? Here’s a trick: You call the recursive function from the initial input to the problem, and if the recursive function is “incorrect/uncomputable/out of bounds”, that’s the initial condition and boundary you need to deal with.

For example, if we call the following two recursive functions.

CoinChange (0) : it can be found that dp[amount-x] causes the array to be out of bounds given 0 elements, so special processing of dp[0] is required.

A call to coinChange(-1) or coinChange(-2) also encounters an out-of-bounds array, indicating that these cases require special handling.

So what are the initial conditions? What is the case as a boundary? The answer is:

If the storage of the result itself is not out of bounds, but out of bounds occurs in the calculation process, it should be taken as the initial condition. For example, DP [0], DP [1];

If the result itself is stored out of bounds, it needs to be treated as a boundary, such as dp[-1].

Of course, for this problem, the initial condition is dp[0] = 0, because when there are only 0 yuan to change, there should only be 0 coins.

6. Compute the order

Interestingly, the order is the simplest, so we just have to take two more steps from our initial conditions using forward derivation. Such as:

Initial conditions: dp[0] = 0

So the input in the following example: Coins [] = [1, 2, 5]. We already know that dp[0] = 0, plus the 3 options we can do, then we get:

Dp [1] = DP [0] + 1 yuan coin = 1

Dp [2] = DP [0] + 2 yuan coin = 1

Dp [5] = DP [0] + 5 yuan coin = 1

So far, recursion doesn’t seem to have been used. When do you use it? Let’s look at the following two cases:

As shown in the figure below, in the first case, DP [5] can be directly obtained by dp[0], with a value of 1.

As shown in the figure below, the second type, DP [5], can be obtained by dp[3] and has a value of 3.

Now, you can see that when you decide which value to take, you need to use the previous recursion.

f(x) = min(f(x-1), f(x-2), f(x-5)) + 1

We just have to take a smaller value.

The complete code shows:

class Solution
{
  public int coinChange(int[] coins, int amount)
  {
    // Set a larger value when there is no solution
    final int INF = Integer.MAX_VALUE / 4;
    int[] dp = new int[amount + 1];

    // Initially set all numbers to unsolvable.
    for (int i = 1; i <= amount; i++) {
      dp[i] = INF;
    }

    // the initial conditions of DP
    dp[0] = 0;

    for (int i = 0; i < amount; i++) {
      for (int y : coins) {
        // Do not cross the boundary
        if (y <= amount && i + y < amount + 1 && i + y >= 0) {
          // Forward derivation of the recursive formula!
          dp[i + y] = Math.min(dp[i + y], dp[i] + 1); }}}return dp[amount] >= INF ? -1: dp[amount]; }}Copy the code