CODEWITHSUNDEEP
c++algorithmrecursiondynamic-programmingcoin-change
Tianyu Lang
Tianyu Lang

Reputation: 21

all solutions to change making with dynamic programming

I was reviewing my handouts for our algorithm class and I started to think about this question:

Given different types of coins with different values, find all coin configurations to add up to a certain sum without duplication.

During class, we solved the problem to find the number of all possible ways for a sum and the least number of coins for a sum. However, we never tried to actually find the solutions.

I was thinking about solving this problem with dynamic programming.

I came with the recursion version(for simplicity I only print the solutions):

void solve(vector<string>& result, string& currSoln, int index, int target, vector<int>& coins)
{
    if(target < 0)
    {
        return;
    }

    if(target == 0)
    {
        result.push_back(currSoln);
    }

    for(int i = index; i < coins.size(); ++i)
    {
        stringstream ss;
        ss << coins[i];
        string newCurrSoln = currSoln + ss.str() + " ";
        solve(result, newCurrSoln, i, target - coins[i], coins);
    }
}

However, I got stuck when trying to use DP to solve the problem. I have 2 major obstacles:

  1. I don't know what data structure I should use to store previous answers
  2. I don't know what my bottom-up procedure(using loops to replace recursions) should look like.

Any help is welcomed and some codes would be appreciated!

Thank you for your time.

Upvotes: 1

Views: 1074

Answers (2)

user1666959
user1666959

Reputation: 1855

It is immediately obvious that you can take a dynamic programming approach. What isn't obvious that in most cases (depending on the denominations of the coins) you can use the greedy algorithm, which is likely to be more efficient. See Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms 2nd ed, problems 16.1.

Upvotes: 0

btilly
btilly

Reputation: 46497

In a dp solution you generate a set of intermediate states, and how many ways there are to get there. Then your answer is the number that wound up in a success state.

So, for change counting, the states are that you got to a specific amount of change. The counts are the number of ways of making change. And the success state is that you made the correct amount of change.

To go from counting solutions to enumerating them you need to keep those intermediate states, and also keep a record in each state of all of the states that transitioned to that one - and information about how. (In the case of change counting, the how would be which coin you added.)

Now with that information you can start from the success state and recursively go backwards through the dp data structures to actually find the solutions rather than the count. The good news is that all of your recursive work is efficient - you're always only looking at paths that succeed so waste no time on things that won't work. But if there are a billion solutions, then there is no royal shortcut that makes printing out a billion solutions fast.

If you wish to be a little clever, though, you can turn this into a usable enumeration. You can, for instance, say "I know there are 4323431 solutions, what is the 432134'th one?" And finding that solution will be quick.

Upvotes: 1

Related Questions