(First hot spot, a little nervous.)

Dynamic Programming (HEREINAFTER referred to as DP) can be said to be one of the most headache problems in the interview, Dynamic Programming itself is often used by many large factories interview questions.

In fact, dynamic programming is a relatively friendly problem among contest algorithm problems, because dynamic programming itself is relatively more dependent on routines and requires less flexibility and inspiration. This article introduces a set of coin questions to familiarize you with dynamic programming and prepare you for future job interviews.

The first question

There's no limit to the number of 1 cent coins, 2 cent coins, 5 cent coins, how many ways you can make up a dollar.Copy the code

This topic is a classic topic of the interview, is also a problem, I very like to use it for the reason of interview questions is: it’s not totally dependent on the topic of dynamic programming, it is very easy to think of ordinary method, in this way, the interview questions can provide well differentiation, unapt appear either will or will not.

The first thing that comes to mind when we look at trivial solutions is the violence count, where we go through the triple loop and we count how many combinations there are. The code is as follows:

let r = 0;
for(let x = 0; x <= 100; x++) 
    for(let y = 0; y <= 50; y++) 
        for(let z = 0; z <= 20; z++)
            if(x + 2 * y + 5 * z === 100)
                ++r;
console.log(r); / / 541
Copy the code

But actually this trivial solution, there’s room for optimization, and let’s see, there’s a very special value in the face value: 1, and this 1 can take any number of values, and there’s only one way to take any number of values, so do we need to loop over this one? The answer, of course, is no. We can write the code like this:

let r = 0;
for(let y = 0; y <= 50; y++) 
    for(let z = 0; z <= (100 - y * 2) / 5; z++)
        ++r;
console.log(r);
Copy the code

Now, we’re going to try to optimize this trivial solution, and since the second loop has to increase by 1 every time, can we just count it out without going through the loop? In fact, if you look at this loop, we can do it by division. The final code is as follows:

let r = 0;
for(let y = 0; y <= 50; y++) 
    r += Math.floor((100 - y * 2) / 5) + 1;
console.log(r); / / 541
Copy the code

To this extent, in fact, the optimization of the ordinary solution is close to the limit, but if we do not consider the particularity of the data, it is extended to a number of coins of any value, whether there is a good solution? Let’s do problem two.

2. Promotion

I have an unlimited number of coins, whose face value is stored in the array values, and now I want to round up the value n, and I want to ask how many ways to round up the value N.Copy the code

And as a generalization of the first problem, by changing constants to variables, we can’t take advantage of the specificity of the data.

All dynamic programming a general train of thought, is the first we reduced the size of the problem to think, to consider how to solve more large-scale, on the one hand, we can solve the problems of the small, familiar with the topic, accumulate experience, and on the other hand, the small problem of the solution, also can be used as the basis of a larger problem.

So, first of all, if values is 1, we have only one coin, values[0], and then we limit n. If n is less than values[0], then obviously there is no solution. If n is equal to values[0], then there is one solution.

If we continue to try to increase the size of n, it is not difficult to find multiples of values[0], the solution is 1, otherwise the solution is 0.

Okay, this conclusion seems like crap, and obviously, it doesn’t seem to work. But it is the key to a much bigger problem.

Now let’s see, what happens if the values array is of length 2?

We’ve already talked about values[0]. Now, let’s look at values[1]. In the same way, can we get multiples of values[1] with one solution? Wait, we’re missing something here, because we already concluded that there’s already one solution for multiples of values[0].

Here we need to think outside the box and consider where the conclusion “integer multiple” came from.

2 values[0], the reason why there is 1 solution, is based on the values[0] 1 times there is 1 solution, add a value [0]. Three times as many values [0], is one kind of solution, is in the values of [0] 2 times, on the basis of one kind of solution, add a values of [0] come out… And so on.

We can imagine a multiple of values[0] starting from the previous “1 solution “and continuing to the new node with values[0] as a step.

For values[1], there are already several “one solution” nodes on the field, so we can start from 0 and multiples of values[0], progressing in steps of values[1].

So the question is, what if there’s overlap? In this case, the node of “one solution” becomes the node of “two solutions”.

Then values[2] goes to Values [3].

We use this idea, to show you a paragraph of animation demonstration (you can modify the parameters to view) :

output.jsbin.com/kasodafifu

Finally we write the code:

function countCoins(values, n) {
    let table = new Array(n + 1).fill(0);
    table[0] = 1;
    for(let value of values) {
        for(let i = value; i <= n; i++)
            table[i] += table[i - value];
    }
    return table[n];
}
console.log(countCoins([1.2.5].100)); / / 541
Copy the code

Problem 3 Constraints

{value:number, count:number}; {value:number, count:number}Copy the code

Ok, so now that we have that foundation, let’s see, if we also constrain the number of coins, what do we do?

The easiest thing to think about, of course, is to start at 0, the same way we started before.

But when we write the code, we find a problem, because the number of coins is limited, when we calculate a value, we have to distinguish whether the node has already used the current value, so we need to take a snapshot of the previous array.

So, is there a better way?

Of course, there is. In fact, if we change the loop to reverse order, then the updated nodes are always behind, and there is no need to distinguish whether the nodes have been updated.

The final code is as follows:

function countCoins(coins, n) {
    let table = new Array(n + 1).fill(0);
    table[0] = 1;
    for(let coin of coins) {
        let {value, count} = coin;
        for(let i = n; i >= 0; i--)
            if(table[i] > 0)
                for(let j = 1; j <= count && i + value * j <= n; j++)
                    table[i + value * j] += table[i];
    }
    return table[n];
}
console.log(countCoins([
    {value:1.count:100},
    {value:2.count:50},
    {value:5.count:20}].100));
Copy the code

Question 4 Variation

There is a pile of coins, want to divide it into two piles, make the difference between the two piles as small as possible, find its minimum difference.Copy the code

And finally, let’s see, this coin splitting problem. In fact, when we solve algorithm problems, after reaching a certain degree of proficiency, the difficulty often lies not in the so-called “dynamic programming”, “greedy”, “divide and conquer” and so on routines, but in the abstraction and understanding of the problem.

The problem of dividing the two piles, keeping the difference between the two piles as small as possible, is not really that different from the problem of pooling money. If the total value of a pile of coins is determined, then splitting two piles is essentially rounding up one value, leaving the other pile. I want the difference between the two piles to be as small as possible, so I want to get as close to 1/2 of the total value as possible.

Since the problem can be converted into a pooling problem, we can use the formula of problem 4 to calculate all the available values below 1/2 of the total value, and then find the node closest to 1/2 of the total value.

Based on the previous question, we can answer this question with very little code change.

function countCoins(coins) {
    
    let total = ((coins) = > {
        let r = 0;
        for(let coin of coins) {
            let {value, count} = coin;
            r += value * count;
        }
        return r;
    })(coins);
    let n = Math.floor(total / 2);
    
    let table = new Array(n + 1).fill(false);
    table[0] = true;
    for(let coin of coins) {
        let {value, count} = coin;
        for(let i = n; i >= 0; i--)
            if(table[i] > 0)
                for(let j = 1; j <= count && i + value * j <= n; j++)
                    table[i + value * j] = true;
    }
    
    for(let i = n; i >= 0; i--){
        if(table[i])
            return total - 2* i; }}console.log(countCoins([
    {value:2.count:1},
    {value:5.count:5}])); / / 3
Copy the code

To consider

Through this article, you should have learned the general routine of the coin problem, but the problems described in this article, are only calculated, there is no specific solution to raise money, interested students can complete this part of the logic, posted in the comments section for everyone to communicate.