» all solutions to change making with dynamic programming
all solutions to change making with dynamic programming
|August 27, 2014
Posted by forumadmin
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)
if(target == 0)
for(int i = index; i < coins.size(); ++i)
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:
- I don’t know what data structure I should use to store previous answers
- 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.
More Related Questions
- Whats the time complexity of this algorithm for Palindrome Partitioning? Palindrome Partitioning
Given a string s, partition s such that every substring of the
partition is a palindrome. Return all possible palindrome
partitioning of s.
Personally I […]
- Determining the complexities given codes Given a snipplet of code, how will you determine the complexities in general. I find myself getting very confused with Big O questions. For example, a very simple question:
for (int i = […]
- What is dynamic programming algorithm for finding a Hamiltonian cycle? What is dynamic programming algorithm for finding a Hamiltonian cycle in a undirected graph?
I have seen somewhere that there exists a algorithm with O(n*2^n) time complextity Asked […]
- How to avoid StackOverflowError caused by the number of recursion calls in Java? I want to solve this problem: https://www.hackerrank.com/challenges/find-median ,i.e. find the median element in unsorted array. To do this I perform quickselect algorithm. My program […]
- Optimum path in a graph to maximize a value I'm trying to come up with a reasonable algorithm for this problem:
Let's say we have bunch of locations. We know the distances between each pair of locations. Each location also has a […]
- Dynamic Programming: USACO Optimal Milking I have been looking at some USACO gold level algorithm problems, and I need someone to help explain the solution of this problem to me. Here is the problem, and the solution is below:
- How many distinct expressions are possible? I came across the following practice problem.
You are free to put any parentheses to the expression anywhere you want and as many as you want. However it should be a valid expression […]
- Finding least number of moves I have the following problem statement:
Given a number n (1 < n < 10^9), what is the least number of
mathematical operations from the set (divide n by 2, divide n by 3,
- Rewriting a recursive function without using recursion I'm rewriting some existing code in a setting where recursive calls are not easily implemented nor desired. (And in Fortran 77, if you must know.) I've thought about making a stack from […]
- What is the most efficient/elegant way to parse a flat table into a tree? Assume you have a flat table that stores an ordered tree hierarchy:
Id Name ParentId Order
1 'Node 1' 0 10
2 'Node 1.1' 1 10
3 'Node 2' […]