Today yanyan posted a question on code War, the general idea is as follows:

A function takes two arguments. The first argument is a number, and the second argument is an array of numbers. All the cases in which the numbers in the array add up to the first argument can be used an infinite number of times. For example, 5, [1, 2, 5], total

  • 1 + 1 + 1 + 1 + 1 = 5
  • 1 plus 1 plus 1 plus 2 is 5
  • 1 plus 2 plus 2 is 5
  • 5 = 5

There are 4 cases, so I return 4. If the first argument is 0, return 1.

Later, I found that there was a similar problem in Leet Code, which was a change problem, which was how many different coins of different denomination could be combined into a number. It’s kind of fun, so I did it, and I used recursion:

const change = function (sum, arr) {
    const nums = arr.sort((a, b) = > a - b);
    return add(sum, nums);
};

const add = function (sum, nums) {
    const min = nums[0];
    if (sum === 0 || sum === min) return 1;

    let res = 0;
    if (nums.includes(sum)) res += 1;

    for (let i = 0; i < nums.length; i++) {
        const last = sum - nums[i];
        if (last >= nums[i]) res += add(last, nums.slice(i));
    }
    return res;
}

Copy the code

Commits successfully on code WAR, but times out on LEet code, poor performance. Then Iyan saw this code in the answer to Code War:

const countChange = (m, c) = > {
  const a = [1].concat(Array(m).fill(0));
  for (let i = 0, l = c.length; i < l; i++) 
    for (let x = c[i], j = x; j <= m; j++) 
      a[j] += a[j - x];
  return a[m];
}

Copy the code

See we are very meng force, think hard for a long time or meng force. So I went online and found a C++ version of the same solution:

using namespace std;

class Solution 
{
public:
    int change(int amount, vector<int>& coins) 
    {
        vector<int> dp(amount + 1.0);
        dp[0] = 1;
        for (int coin : coins) 
        {
            for (inti = coin; i <= amount; ++i) { dp[i] += dp[i - coin]; }}returndp[amount]; }};Copy the code

Dynamic programming (dp) dynamic programming (DP) dynamic programming (DP) dynamic programming (DP)

Dp is an amount + 1 table that records the number of combinations of 0, 1, 2, 3,,, and amount. Dp [0] starts with 1 and all others start with 0.

Next, loop through the currency, recording all combinations from the current currency to amount. The state transition equation is: DP [I] += DP [i-coin]. What does that mean? Let’s say I have a coin of [1, 2, 5] and I have a coin of [1, 2, 5]. If I have a coin of [1, 2, 5] and I have a coin of [1, 2, 5] and I have a coin of [2, 2, 5]. Dp [5]~new~ = DP [5]~old~ + DP [3] and so on.

for (int coin : coins) 
{
    for (inti = coin; i <= amount; ++i) { dp[i] += dp[i - coin]; }}Copy the code

So what this code is saying is I’m going to calculate the number of cases when I take out a 1, I’m going to calculate the number of cases when I take out a 2, I’m going to calculate the number of cases when I take out a 1, I’m going to calculate the number of cases when I take out a 2, I’m going to calculate the number of cases when I take out a 5, The number of cases combined into 5 (plus the number of cases when taking out 1 and 2) gives dp[5], which is the result we want. You may ask that we want DP [5], the middle dp[1] DP [2]… What is the use of DP [4]? In fact, this is the essence of dynamic programming. It will record (cache) the solutions of sub-problems, because these sub-problems will be used many times in the calculation process, so there is no need to calculate every time.

In fact, the general idea of the above solution is similar to the following simple recursion, which is to decompose the problem into sub-problems for solving. The strength of dynamic programming is that it can cache the solutions of sub-problems to avoid repeated calculation and thus improve efficiency.

const countChange = function(money, coins) {
  if (money < 0 || coins.length === 0)
    return 0
  else if (money === 0)
    return 1
  else
    return countChange(money - coins[0], coins) + countChange(money, coins.slice(1))}Copy the code

In the future, when you have a problem that can be decomposed into multiple subproblems, and the subproblems overlap, use dynamic programming.

Oh, I’m so lousy… A dynamic programming problem for a long time…