ASCI Logo
ASCI.Academy
LearnPracticeCompeteCareer
Sign InGet Started

Search ASCI Academy

Universal search across Courses, Lessons, Skills, Projects, Challenges, Competitions, Jobs, Internships, and Users

dsa advanced

Curriculum Index

Current LevelInitiate
0/ 500 XP
Gravit Certificate:
100% Required
  • 1.1 Coin Change Minimum Coins (Tabulation)
•
1
2
3
4
5
6
7
8
9
10
Module 1: Dynamic Programming — 1D & Memoization•Lesson 1

1.1 Coin Change Minimum Coins (Tabulation)

### 1D DP State Definition
Let $dp[i]$ denote the minimum coins needed to form amount $i$:
$$dp[i] = \min_{c \in coins} (dp[i - c] + 1) \quad \text{for } i \ge c$$
Base case: $dp[0] = 0$.

example.pyPython 3.11
def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if i >= c:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1
Python 3.11
•
Interactive Challenge
+100 XP
Challenge Objective

Compute the minimum coins needed to make 11 and print 'MIN_COINS: 3'.

solution.py
UTF-84 SpacesAuto-saved
cpython3.11:~/workspace
CPython 3.11.8 (WASM)
$python3 -u solution.py
Click "Compile & Run" (or press Ctrl + Enter) to compile AST, verify bytecode, and execute the solution.