322. Coin Change

medium · array · dynamic-programming · breadth-first-search · solved 2026.07.14 · 35 sec read

C++

class Solution {public:    int coinChange(vector<int>& coins, int amount) {        std::vector<int> save(amount + 1, 99999999);        save[0] = 0;        for (int i = 0; i <= amount; i++) {            for (auto c : coins) {                if (i - c >= 0) {                    save[i] = min(save[i], save[i - c] + 1);                }            }        }        if (save[amount] == 99999999) return -1;        return save[amount];    }};

This one I first tried doing a 2D knapsack but that did not work. Then tried doing it with recursion but over complicated it with the save array. then just did it iteratively and that worked much better. problem got divided by iteratively solving previous numbers below amount until I get to the needed amount. for each, the memoization was saving the needed coins to get to each amount. at each new number, it is better to either use a new coin to get to desired number from previous number and to keep doing that based on denominations. At that point, if amount index did not solve, then it means that such number is not solvable.