Sicp (Construction and Interpretation of Computer Programs) has such a problem. Since the problem there is in US dollars, I’ll change it to RMB here. The question goes like this: There are 1, 5, 10, 20, and 50 dollar bills. Given any amount of cash, please count all the ways you can count the change.

Zha eye looks, this problem feels very troublesome. How to think. I’m used to thinking like mathematical induction.

Such as

There’s only one dollar, so of course there’s only one way to get change,

If you have 4 dollars, 4 ones, only 1.

If I have 6 yuan, I have 5,1, 1,1,1,1,1,1,1,1,1,1, 2 ways

If it is 11 yuan, that is, (1, 1), (5,5,1), (5, 1 {6}), {11} (1), the four ways.

Let’s say I have 11 dollars

  • This is not possible if the amount in the bill is greater than 11 yuan, so 20 and 50 yuan cannot be used
  • So you can use {10,5,1}
  • So there’s two types of change, there’s 10 dollar bills and there’s no 10 dollar bills, there’s (10,1) one change for the 10 dollar bills, and there’s no 10 dollar bills. Let’s see
  • There’s no exchange for $10 bills, so there’s only exchange for $5 and $1 bills. You can also divide it up into 5 dollar bills and no 5 dollar bills.
  • There are two kinds of five-dollar bills, one is a five-dollar bill, (5,1*6), and the other is two five-dollar bills, (5,5,1).
  • I only have 1 dollar bills, (1 times 11).

So there are 4 ways.

Let me abstract it a little bit more. All amounts of change fall into two categories

  1. Change All the ways (including your own) you can get change after subtracting one note, for example, for 5 yuan, after 11-5, there is (5,5,1); For 20 dollars, 11 minus 20, so you’re going to have zero

  2. Change All forms of change other than one note.

You might want to think about it.

Use the example above to explain.

For example, the change function is F, and array A represents the amount of paper money that can be used (if A is sorted from largest to smallest). The recursion would look something like this.

If I give you 11 dollars, then you can actually figure it out in a pretty mathematical way.

11, F (X = A = [50,20,10,5,1]) F (X = 11, A = [50,20,10,5,1]) = F (11,,5,1 [10]) = F (10, 11 -,5,1 [10]) + F (11, [5, 1]) = 1 + F (11, [5, 1]) = 1 + F (6, [5, 1]) + F (11, [1]) = 4;Copy the code

So you can write your code like this (instead of clipping the elements of the array in your recursive program by using an end variable)

int count(int money, vector<int> &array.int end) {
  if (money < 0) {
    return 0;
  } else if (money == 0) {
    return 1;
  } else if (end == 0) {
    return 0;
  } else {
    return count(money - array[end], array, end) + count(money, array, end - 1); }}int count(int money) {
  vector<int> a = {0.1.5.10.20.50};
  return count(money, a, a.size() - 1);
}
Copy the code

But similar to the previous article, there are double counting problems. So, you can recurse backwards in a bottom-up fashion.

I’m going to store the number of changes in a two-dimensional array, on the horizontal axis of money, and on the vertical axis of paper money. Denoted by v[I][j].

  • If I == 0 or j == 0, then of course it’s 0.
  • If I is equal to 1, if I is equal to 1, if I only use 1 dollar bill, then all of these amounts are expressed one way.
  • If I is equal to 2, we’re saying we’re going to use 1 yuan or 5 yuan. So there are three scenarios
  • J < 5, the amount is less than 5, but there is at least 1 yuan of zero, so v[I][j] = v[i-1][j].
  • J > = 5, the change in the way of zero 5 yuan notes, and so the v [I] [j] [j] [I – 1] = v + v [I] [j – 5)
  • If I is equal to 3, that’s the same thing.

So, you can write code like this.

int count(int money) {
  vector<int> a = {1.5.10.20.50};

  int v[a.size()][money + 1];
  for (int i = 0; i < a.size(); i++) {
    for (int j = 0; j < money + 1; j++) {
      if (i == 0) {
        v[i][j] = 1;
      } else {
        v[i][j] = v[i - 1][j];
        if(j >= a[i]) { v[i][j] += v[i][j - a[i]]; }}}}return v[a.size() - 1][money];
}
Copy the code

This code can also be optimized because v[I][j] = v[i-1][j] for every loop when I > 0; Such a statement, which copies the previous line to the current line, is not really necessary. So you can actually use a one-dimensional array instead of a two-dimensional array.

So it could end up like this.

int count(int money) {
  vector<int> a = {1.5.10.20.50};

  int *v = new int[money + 1];
  for (int i = 0; i < money + 1; i++)
    v[i] = 1;

  for (int i = 1; i < a.size(); i++) {
    for (int j = a[i]; j < money + 1; j++) { v[j] += v[j - a[i]]; }}int res = v[money];
  delete[] v;
  return res;
}
Copy the code