DP will give us quadratic running time, however when we have a coin that can pad and make up every rest of coin changes, then greedy approach is the way to go. Good example would be when we have a cent worth of coin. In this case simply start with the biggest coin first and slide down to smaller coins. Actually, linear running time would only make sense if we know the order of coin value, so in practical we would throw them in a heap so probably O(TlogK)
1 Like
greedy doesn’t work for the following case:
Denominations: {1,3,4,5}
Total amount: 7
Expected Output: 2
Greedy Output: 3