📓
Algorithms
  • Introduction to Data Structures & Algorithms with Leetcode
  • Strings
    • Dutch Flags Problem
      • List Partitoning
    • Counters
      • Majority Vote
      • Removing Parentheses
      • Remove Duplicates from Sorted Array
    • Maths
      • Lone Integer
      • Pigeonhole
      • Check If N and Its Double Exist
      • Find Numbers with Even Number of Digits
    • Two Pointers
      • Remove Element
      • Replace Elements with Greatest Element on Right Side
      • Valid Mountain Array
      • Sort Array by Parity
      • Squares of a Sorted Array
      • Max Consecutive Ones
    • Sliding Window
      • Max Consecutive Ones 3
    • Stacks
      • Balanced Brackets
    • General Strings & Arrays
      • Move Zeros
      • Unique Elements
      • Merge Sorted Array
    • Matrices
      • Valid Square
      • Matrix Search Sequel
  • Trees
    • Untitled
  • Recursion
    • Introduction
    • Backtracking
      • Permutations
  • Dynamic Programming
    • Introduction
    • Minimum (Maximum) Path to Reach a Target
      • Min Cost Climbing Stairs
      • Coin Change
      • Minimum Path Sum
      • Triangle
      • Minimum Cost to Move Chips to The Same Position
      • Consecutive Characters
      • Perfect Squares
    • Distinct Ways
      • Climbing Stairs
      • Unique Paths
      • Number of Dice Rolls with Target Sum
    • Merging Intervals
      • Minimum Cost Tree From Leaf Values
    • DP on Strings
      • Levenshtein Distance
      • Longest Common Subsequence
  • Binary Search
    • Introduction
      • First Bad Version
      • Sqrt(x)
      • Search Insert Position
    • Advanced
      • KoKo Eating Banana
      • Capacity to Ship Packages within D Days
      • Minimum Number of Days to Make m Bouquets
      • Split array largest sum
      • Minimum Number of Days to Make m Bouquets
      • Koko Eating Bananas
      • Find K-th Smallest Pair Distance
      • Ugly Number 3
      • Find the Smallest Divisor Given a Threshold
      • Kth smallest number in multiplication table
  • Graphs
    • Binary Trees
      • Merging Binary Trees
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Inorder Traversal
      • Symmetric Tree
      • Populating Next Right Pointers in Each Node
      • Populating Next Right Pointers in Each Node II
      • 106. Construct Binary Tree from Inorder and Postorder Traversal
      • Serialise and Deserialise a Linked List
      • Maximum Depth of Binary Tree
      • Lowest Common Ancestor of a Binary Tree
    • n-ary Trees
      • Untitled
      • Minimum Height Trees
    • Binary Search Trees
      • Counting Maximal Value Roots in Binary Tree
      • Count BST nodes in a range
      • Invert a Binary Tree
      • Maximum Difference Between Node and Ancestor
      • Binary Tree Tilt
  • Practice
  • Linked Lists
    • What is a Linked List?
    • Add Two Numbers
      • Add Two Numbers 2
    • Reverse a Linked List
    • Tortoise & Hare Algorithm
      • Middle of the Linked List
  • Bitshifting
    • Introduction
  • Not Done Yet
    • Uncompleted
    • Minimum Cost For Tickets
    • Minimum Falling Path Sum
Powered by GitBook
On this page

Was this helpful?

  1. Dynamic Programming
  2. Minimum (Maximum) Path to Reach a Target

Coin Change

PreviousMin Cost Climbing StairsNextMinimum Path Sum

Last updated 4 years ago

Was this helpful?

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.

You may assume that you have an infinite number of each kind of coin.

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int: 
        
        dp = [float("inf")] * (amount + 1)
        
        dp[0] = 0
        
        for y in range(1, amount + 1):
            for coin in coins:
                
                if y - coin < 0:
                    continue
                
                dp[y] = min(dp[y], dp[y - coin] + 1)
                
        if dp[-1] == float("inf"):
            return -1
        
        return dp[-1]

We generate a list the size of amount + 1, and set the first element to 0. We can make 0 coins with 0.

Then we calculate the minimum number of coins for each amount up to the target.

We first check to see if our current amount - the denomination we are checking is below 0. If it is, we cannot use this coin for change so we move onto the next one.

If it's not, the change is either:

  • The current amount (which in first loop is infinite, but in future loops will be different)

  • The current amount take away the denomination + 1. The fewest amount to make y coins, with whatever coin we just took. We want to figure out whatever the best amount it is to make that amount in our dp array. y - coin is the best amount to make that amount. The 1 is because we add one single coin.

If our last value (the target amount) is infinite, we return -1 (as we couldn't change for that amount optimally). Else we return the last value. Our runtime is O(nm) where n is our amount and m is the coins we are given. Space O(n) where n is how big our amount is. Small optimisation We can sort the array, and if our current coin is larger than the amount we break and return as there's no point in going through bigger and bigger coins.

Also see my answer here:

https://leetcode.com/problems/coin-change/
binarysearch | Learn Algorithms Together
Logo