educative.io

Alternative approach for Coin Change

Here’s an approach that avoids the space for a recursive stack and reduces lines by 70%, if that helps the course at all :slight_smile:

def coin_change(coins, total):
    dp = [float('inf')] * (total + 1)
    dp[0] = 0
    for i in range(1, total + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return -1 if dp[-1] == float('inf') else dp[-1]

Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: https://www.educative.io/courses/grokking-coding-interview-patterns-python/coin-change

1 Like

Hello @Isaac_Haseley,

Your approach to solving the “Coin Change” problem is indeed valid and follows a bottom-up strategy, while the approach taught in our lesson employs a top-down approach. When comparing your approach with the one provided in the lesson, both solutions have a time complexity of O(n*m) and a space complexity of O(n).

We’re actively working on improving the quality of the course. Keep sharing such suggestions and feedback; we really appreciate users taking and learning from our courses. Thanks!

Happy learning!

1 Like