The Change Making Problem - Fewest Coins To Make Change Dynamic Programming @BackToBackSWE
The Change Making Problem - Fewest Coins To Make Change Dynamic Programming  @BackToBackSWE
Uploaded January 2019 | Updated November 2026, 3 hours ago
Code & Problem Statement @ backtobackswe.com/platform/content/the-change-making-problem/video?utm_source=youtube&utm_medium=video

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πŸ“Ή Intuitive Video Explanations
πŸƒ Run Code As You Learn
πŸ’Ύ Save Progress
❓New Unseen Questions
πŸ”Ž Get All Solutions

Question: You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Examples:

1
Input:: coins = [1, 2, 5], amount = 11
Output 3

2
Input: coins = [2], amount = 3
Output: -1


Approach 1 (Brute Force)

We can generate all sets of coin frequencies that end up summing to the total amount given the coins that we granted and then take the sequence with the least coins in it.

This is not only harder to implement, but it entails an automatic exponential amount of work to compute all the sets of coin frequencies to only take the best answer (the set with the least coins) from.


Approach 2 (Top Down Dynamic Programming)

Example:
Input:: coins = [1, 2, 5], amount = 11
Output 3

The answer to the subproblem for amount 11 is the same thing as the MINIMUM of the answers to the sub problems with each currency deduced from the original sub problem (11) PLUS ONE since we are acting as if each coin we subtract from 11 is the last coin used to make change.

Not all paths will yield an answer, some will yield an optimal answer.


Complexities (Top Down)

A is the amount to make change for.

n is the total denominations avaliable to make change with.

Time: O( A * n )

For each amount we will approximately be doing n work in trying to deduct each denomination from the current sub problem
Our recursive tree will at maximum have a depth of S (worst case if each call deducts 1 at each call).

Space: O( A )

We answer and store a total of A subproblems in our dynamic programming table to get to our globally optimum answer.


Approach 3 (Bottom Up Dynamic Programming)

Example:
Input:: coins = [1, 2, 5], amount = 11
Output 3

We can also create a dynamic programming table going from the bottom up to the amount we want an answer for.


Complexities (Bottom Up)

A is the amount to make change for.

n is the total denominations avaliable to make change with.

Time: O( A * n )

For each amount we will potentially try each of the denominations (there are n of them).

Space: O( A )

We answer and store a total of A subproblems in our dynamic programming table to get to our globally optimum answer.


++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww

Tuschar Roy: youtube.com/user/tusharroy2525

GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ

Jarvis Johnson: youtube.com/user/VSympathyV

Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
The Change Making Problem - Fewest Coins To Make Change Dynamic ProgrammingInvestigating Heap Sort - Why Is Heap Sort Θ(n * log(n))? An Even Longer Really Long Answer.Build A Min Height BST From A Sorted Array | Coding Interview QuestionLinked Lists Explained | DSA Concept for BeginnersWhat Is Asymptotic Analysis? And Why Does It Matter? A Deeper Understanding of Asymptotic Notation.Implement A Max Stack - A Stack With A .max() API (Similar To Min Stack on LeetCode)All Nodes Distance K In A Binary Tree - Performing Bidirectional Search On A Tree Using A HashtableNetwork Flows: Max-Flow Min-Cut Theorem (& Ford-Fulkerson Algorithm)Coding Interview | Terms to know | API & ADT  #shorts #datastructures #codinginterviewMerge K Sorted Arrays - Min Heap Algorithm (Merge K Sorted Lists on LeetCode)Lowest Common Ancestor Between 2 Binary Tree Nodes (A Recursive Approach)Reverse Polish Notation: Types of Mathematical Notations & Using A Stack To Solve RPN Expressions
Back To Back SWE |

The Change Making Problem - Fewest Coins To Make Change Dynamic Programming

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER