Number of Ways to Make Change

🎯

Number of Ways to Make Change

mediumDPAmazonGoogle

Imagine you have an unlimited supply of coins of different denominations, and you want to find out how many distinct ways you can make a certain amount of money. This problem models that real-world scenario.

💡 This problem is a classic example of dynamic programming where beginners often struggle to understand why greedy approaches fail and how to count combinations rather than just check feasibility. It requires careful thinking about overlapping subproblems and how to build solutions incrementally.

📋

Problem Statement

Given an integer amount and a list of coin denominations, return the number of distinct ways to make up that amount using any number of coins. You can use each coin denomination an unlimited number of times. The order of coins does not matter.

1 ≤ amount ≤ 10^51 ≤ number of coin denominations ≤ 1001 ≤ coin denomination value ≤ amount

💡

Example

Input"amount = 5, coins = [1, 2, 5]"

Output4

The four ways are: 5=5; 5=2+2+1; 5=2+1+1+1; 5=1+1+1+1+1

• amount = 0, coins = [1,2,3] → 1 (empty combination)
• amount = 3, coins = [] → 0 (no coins to use)
• amount = 7, coins = [2,4] → 0 (no combination sums to 7)
• amount = 1, coins = [2,3,5] → 0 (coins larger than amount)

🔁

Why DP?

Why greedy fails:

Greedy fails because choosing the largest coin first does not guarantee all combinations are counted. For example, amount=5 with coins=[1,2,5]: greedy picks 5 once, but misses combinations like 2+2+1.

DP state:

dp[i][w] = number of ways to make amount w using the first i coin denominations.

Recurrence:dp[i][w] = dp[i-1][w] + dp[i][w - coins[i-1]] if w >= coins[i-1], else dp[i-1][w]

The number of ways to make amount w using first i coins equals ways without using the ith coin plus ways using at least one ith coin.

⚠️

Common Mistakes

Using greedy approach

Misses valid combinations, returns incorrect count

✅ Use DP to count all combinations

Not handling base case amount=0 correctly

Returns 0 instead of 1, missing empty combination

✅ Initialize dp[0] = 1 or return 1 when amount=0 in recursion

Counting permutations instead of combinations

Overcounts ways, giving wrong results

✅ Iterate coins outer loop, amounts inner loop to count combinations

Using 1D dp but iterating amounts backwards

Misses some combinations or counts duplicates

✅ Iterate amounts forward when coins are unlimited

Not memoizing in top-down approach

Exponential time, TLE

✅ Add memo dictionary or map to cache results

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive structure and why naive solutions are inefficient.

Intuition

Try all combinations by either including or excluding each coin for the current amount recursively.

Algorithm

1. If amount is 0, return 1 as a valid combination is found.
2. If amount is negative or no coins left, return 0 as no valid combination.
3. Recursively count ways by including the current coin and excluding it.
4. Sum both counts to get total ways.

💡 The recursion explores all subsets, which is conceptually simple but computationally expensive.

Recurrence:ways(i, amount) = ways(i-1, amount) + ways(i, amount - coins[i])

</>

Code

def count_ways(coins, n, amount):
    if amount == 0:
        return 1
    if amount < 0 or n == 0:
        return 0
    return count_ways(coins, n - 1, amount) + count_ways(coins, n, amount - coins[n - 1])

# Driver code
coins = [1, 2, 5]
amount = 5
print(count_ways(coins, len(coins), amount))

Line Notes

if amount == 0:Base case: exact amount formed means one valid way

if amount < 0 or n == 0:No valid way if amount negative or no coins left

return count_ways(coins, n - 1, amount)Exclude current coin and recurse

return count_ways(coins, n, amount - coins[n - 1])Include current coin and recurse

public class Solution {
    public static int countWays(int[] coins, int n, int amount) {
        if (amount == 0) return 1;
        if (amount < 0 || n == 0) return 0;
        return countWays(coins, n - 1, amount) + countWays(coins, n, amount - coins[n - 1]);
    }
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 5;
        System.out.println(countWays(coins, coins.length, amount));
    }
}

Line Notes

if (amount == 0) return 1;Base case: found a valid combination

if (amount < 0 || n == 0) return 0;No valid combination if amount negative or no coins

return countWays(coins, n - 1, amount)Exclude current coin and recurse

return countWays(coins, n, amount - coins[n - 1])Include current coin and recurse

#include <iostream>
using namespace std;

int countWays(int coins[], int n, int amount) {
    if (amount == 0) return 1;
    if (amount < 0 || n == 0) return 0;
    return countWays(coins, n - 1, amount) + countWays(coins, n, amount - coins[n - 1]);
}

int main() {
    int coins[] = {1, 2, 5};
    int amount = 5;
    int n = sizeof(coins) / sizeof(coins[0]);
    cout << countWays(coins, n, amount) << endl;
    return 0;
}

Line Notes

if (amount == 0) return 1;Base case: valid combination found

if (amount < 0 || n == 0) return 0;No valid combination if amount negative or no coins

return countWays(coins, n - 1, amount)Exclude current coin and recurse

return countWays(coins, n, amount - coins[n - 1])Include current coin and recurse

function countWays(coins, n, amount) {
    if (amount === 0) return 1;
    if (amount < 0 || n === 0) return 0;
    return countWays(coins, n - 1, amount) + countWays(coins, n, amount - coins[n - 1]);
}

const coins = [1, 2, 5];
const amount = 5;
console.log(countWays(coins, coins.length, amount));

Line Notes

if (amount === 0) return 1;Base case: found a valid way

if (amount < 0 || n === 0) return 0;No valid way if amount negative or no coins

return countWays(coins, n - 1, amount)Exclude current coin and recurse

return countWays(coins, n, amount - coins[n - 1])Include current coin and recurse

⏱

Complexity

TimeO(2^n) exponential due to exploring all subsets

SpaceO(n) recursion stack depth

Each call branches into two, leading to exponential calls; stack depth is at most number of coins.

💡 For n=20 coins, this means over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem structure.

🧠

Top-Down Memoization

💡 Memoization avoids recomputing the same subproblems by caching results, drastically improving efficiency.

Intuition

Store results of recursive calls in a table keyed by coin index and amount to reuse them.

Algorithm

1. Initialize a memo table to store results for each (coin index, amount).
2. If amount is 0, return 1.
3. If amount < 0 or no coins left, return 0.
4. If result in memo, return it to avoid recomputation.
5. Otherwise, compute ways by excluding and including current coin, store in memo.

💡 Memoization converts exponential recursion into polynomial time by caching.

Recurrence:ways(i, amount) = ways(i-1, amount) + ways(i, amount - coins[i])

</>

Code

def count_ways_memo(coins, n, amount, memo=None):
    if memo is None:
        memo = {}
    if amount == 0:
        return 1
    if amount < 0 or n == 0:
        return 0
    if (n, amount) in memo:
        return memo[(n, amount)]
    memo[(n, amount)] = count_ways_memo(coins, n - 1, amount, memo) + count_ways_memo(coins, n, amount - coins[n - 1], memo)
    return memo[(n, amount)]

# Driver code
coins = [1, 2, 5]
amount = 5
print(count_ways_memo(coins, len(coins), amount))

Line Notes

memo = {}Initialize memo dictionary to cache results

if (n, amount) in memo:Check if result already computed to avoid recomputation

memo[(n, amount)] = ...Store computed result in memo

return memo[(n, amount)]Return cached or newly computed result

import java.util.HashMap;
import java.util.Map;

public class Solution {
    static Map<String, Integer> memo = new HashMap<>();
    public static int countWaysMemo(int[] coins, int n, int amount) {
        if (amount == 0) return 1;
        if (amount < 0 || n == 0) return 0;
        String key = n + "," + amount;
        if (memo.containsKey(key)) return memo.get(key);
        int res = countWaysMemo(coins, n - 1, amount) + countWaysMemo(coins, n, amount - coins[n - 1]);
        memo.put(key, res);
        return res;
    }
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 5;
        System.out.println(countWaysMemo(coins, coins.length, amount));
    }
}

Line Notes

static Map<String, Integer> memoMemo map to cache results keyed by coin index and amount

if (memo.containsKey(key))Return cached result if available

memo.put(key, res);Store computed result in memo

return res;Return computed or cached result

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

unordered_map<string, int> memo;

int countWaysMemo(int coins[], int n, int amount) {
    if (amount == 0) return 1;
    if (amount < 0 || n == 0) return 0;
    string key = to_string(n) + "," + to_string(amount);
    if (memo.find(key) != memo.end()) return memo[key];
    memo[key] = countWaysMemo(coins, n - 1, amount) + countWaysMemo(coins, n, amount - coins[n - 1]);
    return memo[key];
}

int main() {
    int coins[] = {1, 2, 5};
    int amount = 5;
    int n = sizeof(coins) / sizeof(coins[0]);
    cout << countWaysMemo(coins, n, amount) << endl;
    return 0;
}

Line Notes

unordered_map<string, int> memo;Memo map to cache results

if (memo.find(key) != memo.end())Return cached result if found

memo[key] = ...Store computed result in memo

return memo[key];Return cached or computed result

const memo = new Map();
function countWaysMemo(coins, n, amount) {
    if (amount === 0) return 1;
    if (amount < 0 || n === 0) return 0;
    const key = n + ',' + amount;
    if (memo.has(key)) return memo.get(key);
    const res = countWaysMemo(coins, n - 1, amount) + countWaysMemo(coins, n, amount - coins[n - 1]);
    memo.set(key, res);
    return res;
}

const coins = [1, 2, 5];
const amount = 5;
console.log(countWaysMemo(coins, coins.length, amount));

Line Notes

const memo = new Map();Memo map to cache results

if (memo.has(key))Return cached result if available

memo.set(key, res);Store computed result in memo

return res;Return cached or computed result

⏱

Complexity

TimeO(n * amount) due to memoization caching each state once

SpaceO(n * amount) for memo table and recursion stack

Memoization ensures each (coin index, amount) pair is computed once.

💡 For amount=1000 and 10 coins, this means about 10,000 computations, which is efficient.

Interview Verdict: Accepted

Memoization is a practical optimization that makes the solution efficient enough for interviews.

🧠

Bottom-Up Tabulation

💡 Tabulation builds the solution iteratively from smaller subproblems, which is often easier to debug and understand than recursion.

Intuition

Use a 2D dp table where dp[i][w] stores ways to make amount w using first i coins, filling it row by row.

Algorithm

1. Initialize dp table with dp[0][0] = 1 (0 amount with 0 coins).
2. Iterate over coins and amounts, filling dp[i][w].
3. For each cell, add ways excluding current coin (dp[i-1][w]) and including it (dp[i][w - coin]).
4. Return dp[n][amount] as final answer.

💡 Tabulation explicitly shows how solutions build up from base cases.

Recurrence:dp[i][w] = dp[i-1][w] + dp[i][w - coins[i-1]] if w >= coins[i-1], else dp[i-1][w]

</>

Code

def count_ways_tab(coins, amount):
    n = len(coins)
    dp = [[0] * (amount + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1
    for i in range(1, n + 1):
        for w in range(amount + 1):
            dp[i][w] = dp[i - 1][w]
            if w >= coins[i - 1]:
                dp[i][w] += dp[i][w - coins[i - 1]]
    return dp[n][amount]

# Driver code
coins = [1, 2, 5]
amount = 5
print(count_ways_tab(coins, amount))

Line Notes

dp = [[0] * (amount + 1) for _ in range(n + 1)]Create dp table with rows for coins and columns for amounts

for i in range(n + 1): dp[i][0] = 1Base case: one way to make amount 0 (empty set)

dp[i][w] = dp[i - 1][w]Ways excluding current coin

dp[i][w] += dp[i][w - coins[i - 1]]Add ways including current coin if possible

public class Solution {
    public static int countWaysTab(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= amount; w++) {
                dp[i][w] = dp[i - 1][w];
                if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];
            }
        }
        return dp[n][amount];
    }
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 5;
        System.out.println(countWaysTab(coins, amount));
    }
}

Line Notes

int[][] dp = new int[n + 1][amount + 1];Initialize dp table for coins and amounts

for (int i = 0; i <= n; i++) dp[i][0] = 1;Base case: one way to make amount 0

dp[i][w] = dp[i - 1][w];Ways excluding current coin

if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];Add ways including current coin

#include <iostream>
#include <vector>
using namespace std;

int countWaysTab(vector<int>& coins, int amount) {
    int n = coins.size();
    vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
    for (int i = 0; i <= n; i++) dp[i][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= amount; w++) {
            dp[i][w] = dp[i - 1][w];
            if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];
        }
    }
    return dp[n][amount];
}

int main() {
    vector<int> coins = {1, 2, 5};
    int amount = 5;
    cout << countWaysTab(coins, amount) << endl;
    return 0;
}

Line Notes

vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));Create 2D dp table initialized to 0

for (int i = 0; i <= n; i++) dp[i][0] = 1;Base case: one way to make amount 0

dp[i][w] = dp[i - 1][w];Ways excluding current coin

if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];Add ways including current coin

function countWaysTab(coins, amount) {
    const n = coins.length;
    const dp = Array.from({ length: n + 1 }, () => Array(amount + 1).fill(0));
    for (let i = 0; i <= n; i++) dp[i][0] = 1;
    for (let i = 1; i <= n; i++) {
        for (let w = 0; w <= amount; w++) {
            dp[i][w] = dp[i - 1][w];
            if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];
        }
    }
    return dp[n][amount];
}

const coins = [1, 2, 5];
const amount = 5;
console.log(countWaysTab(coins, amount));

Line Notes

const dp = Array.from({ length: n + 1 }, () => Array(amount + 1).fill(0));Initialize 2D dp array

for (let i = 0; i <= n; i++) dp[i][0] = 1;Base case: one way to make amount 0

dp[i][w] = dp[i - 1][w];Ways excluding current coin

if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];Add ways including current coin

⏱

Complexity

TimeO(n * amount) iterating over coins and amounts

SpaceO(n * amount) for dp table

Each dp cell computed once using previously computed cells.

💡 For amount=1000 and 10 coins, about 10,000 operations, efficient for interviews.

Interview Verdict: Accepted

Tabulation is a preferred approach for clarity and iterative control.

🧠

Space Optimized Bottom-Up (1D DP)

💡 We can reduce space by using a 1D dp array since current row depends only on current and previous states in a specific order.

Intuition

Use a single array where dp[w] represents ways to make amount w, updating it as we iterate over coins.

Algorithm

1. Initialize dp array of size amount+1 with dp[0] = 1.
2. For each coin, iterate amounts from coin value to amount.
3. Update dp[w] by adding dp[w - coin] to count ways including current coin.
4. Return dp[amount] as final answer.

💡 This approach uses forward iteration to avoid counting duplicates and saves space.

Recurrence:dp[w] += dp[w - coin]

</>

Code

def count_ways_space_opt(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for w in range(coin, amount + 1):
            dp[w] += dp[w - coin]
    return dp[amount]

# Driver code
coins = [1, 2, 5]
amount = 5
print(count_ways_space_opt(coins, amount))

Line Notes

dp = [0] * (amount + 1)Initialize 1D dp array for amounts

dp[0] = 1Base case: one way to make amount 0

for coin in coins:Iterate over each coin denomination

dp[w] += dp[w - coin]Add ways including current coin

public class Solution {
    public static int countWaysSpaceOpt(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int w = coin; w <= amount; w++) {
                dp[w] += dp[w - coin];
            }
        }
        return dp[amount];
    }
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 5;
        System.out.println(countWaysSpaceOpt(coins, amount));
    }
}

Line Notes

int[] dp = new int[amount + 1];Initialize 1D dp array

dp[0] = 1;Base case: one way to make amount 0

for (int coin : coins)Iterate over coins

dp[w] += dp[w - coin];Update ways including current coin

#include <iostream>
#include <vector>
using namespace std;

int countWaysSpaceOpt(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;
    for (int coin : coins) {
        for (int w = coin; w <= amount; w++) {
            dp[w] += dp[w - coin];
        }
    }
    return dp[amount];
}

int main() {
    vector<int> coins = {1, 2, 5};
    int amount = 5;
    cout << countWaysSpaceOpt(coins, amount) << endl;
    return 0;
}

Line Notes

vector<int> dp(amount + 1, 0);Initialize 1D dp vector

dp[0] = 1;Base case: one way to make amount 0

for (int coin : coins)Iterate over coins

dp[w] += dp[w - coin];Add ways including current coin

function countWaysSpaceOpt(coins, amount) {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (const coin of coins) {
        for (let w = coin; w <= amount; w++) {
            dp[w] += dp[w - coin];
        }
    }
    return dp[amount];
}

const coins = [1, 2, 5];
const amount = 5;
console.log(countWaysSpaceOpt(coins, amount));

Line Notes

const dp = new Array(amount + 1).fill(0);Initialize 1D dp array

dp[0] = 1;Base case: one way to make amount 0

for (const coin of coins)Iterate over coins

dp[w] += dp[w - coin];Update ways including current coin

⏱

Complexity

TimeO(n * amount) iterating over coins and amounts

SpaceO(amount) reduced from 2D to 1D

Only one dp array is maintained, updated in place.

💡 For amount=1000, this uses 1000 integers instead of 100,000 in 2D.

Interview Verdict: Accepted

Space optimization is a common interview follow-up and shows deep understanding.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, code the bottom-up tabulation or space-optimized approach for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down Memoization	O(n * amount)	O(n * amount)	Possible but less likely	Yes	Good for explaining optimization
3. Bottom-Up Tabulation	O(n * amount)	O(n * amount)	No	Yes	Preferred approach to code
4. Space Optimized Bottom-Up	O(n * amount)	O(amount)	No	No (without extra tracking)	Mention or code if asked for optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and examples.Explain brute force recursion to show problem structure.Introduce memoization to optimize overlapping subproblems.Present bottom-up tabulation for iterative clarity.Discuss space optimization as an advanced technique.Write clean code and test edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Understanding of DP concepts, ability to optimize naive solutions, clarity in explanation, and coding accuracy.

Common Follow-ups

• How to handle large amounts with modulo arithmetic → use modulo to avoid overflow.
• Count permutations instead of combinations → change iteration order to count order-sensitive ways.

💡 These follow-ups test your flexibility with DP and understanding of problem variations.

🔍

Pattern Recognition

When to Use

1) Asked to count ways or number of combinations; 2) Unlimited use of items (coins); 3) Target sum or amount given; 4) Order of items does not matter.

Signature Phrases

number of ways to make changeunlimited supply of coinscount combinations

NOT This Pattern When

Problems asking for minimum coins or maximum value are optimization, not counting problems.

Similar Problems

Coin Change II - counts combinations similarlyCombination Sum IV - counts permutations (order matters)Partition Equal Subset Sum - subset sum feasibility

Practice

1. Consider the following code snippet for the coin change problem. What is the value of dp[5] after the outer loop iteration i=5 completes when coins = [1, 2, 5] and amount = 5?

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], 1 + dp[i - coin])
    return dp[amount]

print(coinChange([1,2,5], 5))

easy

A. 5

B. 2

C. 3

D. 1

Solution

1. Step 1: Trace dp array updates up to i=5

   dp[0]=0; For i=1: dp[1]=min(inf,1+dp[0])=1; i=2: dp[2]=min(inf,1+dp[1],1+dp[0])=1; i=3: dp[3]=min(inf,1+dp[2],1+dp[1])=2; i=4: dp[4]=min(inf,1+dp[3],1+dp[2])=2; i=5: dp[5]=min(inf,1+dp[4],1+dp[3],1+dp[0])=min(inf,3,3,1)=1

2. Step 2: Confirm dp[5] value

   Using coin 5 directly gives dp[5]=1, which is minimal.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   dp[5] = 1 coin (coin 5) [OK]

Hint: Direct coin equal to amount sets dp[amount] to 1 [OK]

Common Mistakes:

• Off-by-one errors in indexing dp
• Ignoring direct coin match

2. Consider the following Python function implementing the minimum subset sum difference problem. What is the returned output when the input array is [1, 6, 11, 5]?

easy

A. 5

B. 3

C. 0

D. 1

Solution

1. Step 1: Calculate total_sum and half

   total_sum = 1 + 6 + 11 + 5 = 23, half = 11

2. Step 2: Identify largest achievable sum ≤ half

   DP finds sums achievable: 0,1,5,6,11,... Largest w ≤ 11 with dp[w] = true is 11.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Difference = 23 - 2*11 = 1 [OK]

Hint: Check largest achievable sum ≤ half total sum [OK]

Common Mistakes:

• Off-by-one in half calculation
• Misreading dp array updates

3. The following code attempts to solve the job scheduling problem optimally. Which line contains a subtle bug that can cause incorrect results?

medium

A. Line 11: Using bisect_right to find compatible job index

B. Line 7: Creating ends array from job end times

C. Line 4: Sorting jobs by start time instead of end time

D. Line 14: Calculating dp[i] as max of take and skip

Solution

1. Step 1: Identify sorting criteria

   Jobs must be sorted by end time for binary search on ends array to work correctly.

2. Step 2: Check sorting line

   Line 4 sorts by start time, breaking DP dependencies and binary search correctness.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting by start time causes incorrect compatible job lookups and suboptimal profits [OK]

Hint: Sort jobs by end time, not start time [OK]

Common Mistakes:

• Sorting by start time
• Incorrect binary search bounds
• Ignoring dp base cases

4. What is the time complexity of the optimal bottom-up dynamic programming solution for the problem, given strs has length l, and the constraints are m zeros and n ones?

medium

A. O(l * (m + n))

B. O(l * m * n)

C. O(l * m * n * max_length_of_string)

D. O(2^l)

Solution

1. Step 1: Identify loops in the code

   Outer loop iterates over all strings (l), inner loops iterate over m and n capacities.

2. Step 2: Calculate total operations

   Each string causes updates over a 2D dp array of size (m+1)*(n+1), so total complexity is O(l * m * n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Nested loops over l, m, n -> O(l * m * n) [OK]

Hint: Nested loops over strings and both capacities multiply complexities [OK]

Common Mistakes:

• Confusing sum with product of m and n
• Including string length in complexity unnecessarily

5. Suppose the stones can be used multiple times (unlimited quantity of each stone). Which modification to the DP approach correctly computes the minimal last stone weight?

hard

A. Use a greedy approach smashing largest stones repeatedly

B. Keep the inner loop iterating backwards as in 0/1 knapsack to avoid reuse

C. Change the inner loop to iterate forwards from weight to half, allowing reuse of stones

D. Use recursion without memoization to explore all combinations with reuse

Solution

1. Step 1: Understand difference between 0/1 and unbounded knapsack

   For unlimited reuse, inner loop must iterate forwards to allow multiple counts of the same stone.

2. Step 2: Modify DP accordingly

   Iterating forwards from weight to half updates dp[w] using dp[w - weight] from the same iteration, enabling reuse.

3. Step 3: Why other options fail

   Backward iteration prevents reuse; greedy is incorrect; recursion without memoization is inefficient.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Forward iteration in inner loop enables unlimited stone reuse [OK]

Hint: Unbounded knapsack -> inner loop forwards [OK]

Common Mistakes:

• Using backward iteration causing no reuse
• Trying greedy which is incorrect
• Ignoring memoization leading to TLE