Neetcode - Coin Change

Code with purpose, build with passion.

This problem falls under the category of Dynamic Programming (DP). In this case, we can think of it as an n-ary tree problem, where we traverse each path until it is no longer possible to continue tracking a specific one. Below, I provide both my attempted approach and an optimized solution generated by a language model.

class Solution {
    unordered_map<int, int> _memo;
public:
    int coinChange(vector<int>& coins, int amount) {
        int min_coins = -1;
        dfs(coins, amount, 0, min_coins, _memo);
        return min_coins;
    }

    void dfs(vector<int>& coins, int remain_amount, int count, int &min_coins, unordered_map<int, int>& _memo) {
        if (remain_amount == 0) {
            if (min_coins == -1 || count < min_coins) {
                min_coins = count;
            }
            return;
        } else if (remain_amount < 0) {
            return;
        }

        if (_memo.count(remain_amount) && _memo[remain_amount] <= count) {
            return;
        }

        _memo[remain_amount] = count;

        for (int coin : coins) {
            dfs(coins, remain_amount - coin, count + 1, min_coins, _memo);
        }
    }
};

When I draw the tree diagram, the solution becomes clearer and naturally lends itself to a recursive approach. However, recursive solutions often encounter Time Limit Exceeded (TLE) errors, so memoization is necessary to improve efficiency. The terminal condition is determined by the remaining amount — it tells us when to stop the recursion. We should only update min_coins with the current count when min_coins is -1 or greater than the current count value. To account for using the same coin multiple times (e.g., using twelve 1-coin values), a for loop is used to iterate through the available coin options.

class Solution {
  unordered_map<int, int> _memo;

public:
  int coinChange(vector<int> &coins, int amount) {
    if (amount == 0)
      return 0;

    int least_coin = dfs(coins, amount);
    return least_coin == INT_MAX ? -1 : least_coin;
  }

  int dfs(vector<int> &coins, int remain) {
    if (remain < 0)
      return INT_MAX;
    if (remain == 0)
      return 0;
    if (_memo.count(remain))
      return _memo[remain];

    int min_coins = INT_MAX;
    for (int coin : coins) {
      int sub = dfs(coins, remain - coin);
      if (sub != INT_MAX) {
        min_coins = min(min_coins, sub + 1);
      }
    }

    _memo[remain] = min_coins;
    return min_coins;
  }
};

The second one is the optimized version of the initial solution. In this approach, we use the system's INT_MAX value as a flag to represent an unreachable state, and we continuously update min_coins with the minimum among all possible coin combinations. We also memoize the results by storing the minimum number of coins required for each remaining amount—for example, _memo[5] = 1 if the coin 5 exists in the given set. Additionally, a Breadth-First Search (BFS) approach is also worth considering, as it can be efficient for this type of problem.

class SolutionBFS {
public:
  int coinChange(vector<int> &coins, int amount) {
    if (amount == 0)
      return 0;

    queue<int> q;
    q.push(0);

    vector<bool> seen(amount + 1, false);
    seen[0] = true;

    int min_coins = 0;
    while (!q.empty()) {
      ++min_coins;

      int size = q.size();
      for (int i = 0; i < size; ++i) {
        int current = q.front();
        q.pop();

        for (int coin : coins) {
          int next = current + coin;
          if (next == amount)
            return min_coins;
          if (next > amount || seen[next])
            continue;
          seen[next] = true;
          q.push(next);
        }
      }
    }

    return -1;
  }
};

This method traverses the search space level by level using the coins. At each level, it checks the first value in the queue against all available coins to see if any combination sums up to the target amount. The min_coins count is incremented with each level to track the number of steps taken. Additionally, a simple memoization technique (e.g., a visited set or array) is used to avoid revisiting the same values.

Conclusion

This problem provides an interesting opportunity to review both DFS and BFS approaches, especially with the core concept of DP. DP problems tend to be challenging to grasp at first, and even though I have solved several similar problems, I still find them difficult to master. However, as the saying goes, “What you fear most is where you will grow.” I hope to become more proficient at solving these types of problems soon. After all, RL is closely related to DP.