Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

One-Dimensional DP

Guide 6 of 6 · Path 6 of 6

← PreviousNext pattern: Two-Dimensional DP →

Interactive

Mental model

A worked animation for this problem. Scrub steps or press space to pause; re-tell the invariant out loud.

Step 1 of 8
0
1
2
3
4
5
6

dp[0]=0, else inf

Fewest coins for amount 6 using coins {1,2,5}.

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumone-dimensional-dp

Coin Change

Problem (restated)

Given coin denominations and amount, return the fewest coins to make that amount, or -1 if impossible. Unlimited coins of each denomination.

Intuition

dp[x] = min coins to make x. dp[0]=0; for each amount, try each coin: dp[x] = min(dp[x], dp[x-coin]+1).

Approaches

Bottom-up DP

Tested only
Time O(amount · coins)Space O(amount)

Idea. Initialize dp with ∞ except dp[0]=0. Relax transitions for every coin.

Walkthrough. coins=[1,2,5], amount=11 → dp[11]=3 (5+5+1).

Trade-offs. Standard optimal. BFS by coin count also works (shortest path in coin graph).

Solution
export function coinChange(coins: number[], amount: number): number {
  const INF = amount + 1;
  const dp = new Array<number>(amount + 1).fill(INF);
  dp[0] = 0;
  for (let x = 1; x <= amount; x++) {
    for (const c of coins) {
      if (c <= x) dp[x] = Math.min(dp[x]!, dp[x - c]! + 1);
    }
  }
  return dp[amount]! > amount ? -1 : dp[amount]!;
}

export function coinChange(coins: number[], amount: number): number {
  const INF = amount + 1;
  const dp = new Array<number>(amount + 1).fill(INF);
  dp[0] = 0;
  for (let x = 1; x <= amount; x++) {
    for (const c of coins) {
      if (c <= x) dp[x] = Math.min(dp[x]!, dp[x - c]! + 1);
    }
  }
  return dp[amount]! > amount ? -1 : dp[amount]!;
}

Template connection

Classic unbounded knapsack / 1D DP.

Reflection