Dynamic Programming
DP State Tables
Watch tabulation fill one state at a time with dependencies, current result, and per-step time and space complexity.
O(amount * coins)
State 00
State 1inf
State 2inf
State 3inf
State 4inf
State 5inf
State 6inf
State 7inf
State 8inf
State 9inf
State 10inf
State 11inf
Result
0
Time
O(amount * coins)
Space
O(amount)
Step Note
Find minimum coins for amount 11.
function coinChange(coins: number[], amount: number) {
const dp = Array(amount + 1).fill(Infinity)
dp[0] = 0
for (const coin of coins) {
for (let current = coin; current <= amount; current++) {
dp[current] = Math.min(dp[current], dp[current - coin] + 1)
}
}
return dp[amount]
}