I thought I was ready for this, boy was I naive.

Here are some solutions I found (not written by me)

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // set a value that is guaranteed to bigger than the possible answer
        // the smallest possible coin value is 1, so there may not be anwer that has to have amount+1 coins to build up the amount
        int ub = amount + 1;
        // record the smallest coins to get the each amount
        vector<int> dp(amount + 1, ub);
        // sort the coins so we could consider less cases
        sort(coins.begin(), coins.end());
        // start from 0 coins
        dp[0] = 0;
        // compute each amount coin numbers from 0
        for (int i = 1; i <= amount; ++i) {
            // consider the last coin as each coins value
            for (int j = 0; j < coins.size(); ++j) {
                // ensure dp[i - coins[j]] is valid
                if (i-coins[j]<0) {
                    break;
                }
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
        
        return dp[amount]!=ub?dp[amount]:-1;
    }
};

Instead of doing a dfs type search, this solution started filling the memoization table from amount = 1 ~ amount, before the memoization process, it initialized a vector with size amount+1 and has int amount+1 in each slot, the number in the slots indicate the upper bound of how many coins are needed. (50 dollars would need at most 50 coins, so 51 would be a safe upper bound)

Next, it starts iterating through 1 ~ amount, for each iteration, an inner loop that loops through the coins give rise to the psedo code below: dp[i] = 1 + min(dp[i - coins[0]],dp[i - coins[1]],dp[i - coins[2]], . . . ,dp[i - coins[coins.size()-1]])

Once i - coins[j] < 0, indicates that starting from this coin, the amount of the coin is bigger than the target, hence no need to keep iterating through the coins array (the coins array is in ascending order after sort() )

class Solution {
private:
    int check(vector<int>& coins, short index, int cnt, int target){
        long sum = (long) coins[index]*cnt;
        if (target == sum) return true;
        else if (sum > target) {
            if(index == 0) return false;//more coins than required .

            for (short i = cnt; i>0; i--){
                long take = target - (long)coins[index]*(cnt-i);
                if (take < 0) break;
                int r =  take;
                if (check(coins, index-1, i, r)) return true;    
            }
        }
        return false;//less coins than needed
    }
public:
    int coinChange(vector<int>& coins, int amt) {
        if(amt&1) {
            short i = 0;
            for(; i < coins.size() ; ++i) {
                if(coins[i]&1) break;
            }
            if(i == coins.size()) return -1;
        }

        sort(coins.begin() , coins.end());

        int s = amt/coins.back();
        int e = amt/coins.front();
        int ans = -1;
        for(int cnt = s; cnt <= e ; ++cnt) {
            if(check(coins, coins.size() - 1, cnt , amt)) return cnt;
        }
        return -1;
    }
};