The top solutions are not optimized for cases where amount is a huge value.


  • 0
    A

    Actually, there could be a lot of cases, where amount could be a huge value, while the coins are relatively small.
    If you DP through 0 - amount, it will be a huge waste of resources. An optimization can be made, to only calculate the first min(amount, LCM(coin)) numbers. And then fill the rest of the results using the largest coin.

    This is a temp solution I didn't clean up yet, but it proves the idea

    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            if (coins.size() == 0) return -1;
            if (amount == 0) return 0;
    
            long iLcd = coins[0], iLcm = coins[0];
            for (int i = 1; i < coins.size(); ++i) {
                iLcd = lcd(iLcd, coins[i]);
                iLcm = lcm(iLcm, coins[i]);
            }
            if (amount % iLcd != 0) return -1;
            if (iLcd != 1) {
                transform(coins.begin(), coins.end(), coins.begin(), [&iLcd](int coin) -> int { return coin / iLcd; });
                return coinChange(coins, amount / iLcd);
            }
            sort(coins.begin(), coins.end());
            int smallest = coins[0];
            int largest = coins.back();
            if (largest > amount) {
                while (coins.back() > amount) {
                    coins.pop_back();
                }
                return coinChange(coins, amount);
            }
            cout << "lcd: " << iLcd << ", lcm: " << iLcm << ", amount: " << amount << endl;
            vector<int> dp((int)min(iLcm, (long)(amount + 1)), -2);
            dp[0] = 0;
            std::function<int(int)> dpLambda = [&dp, &coins, &iLcm, &largest, &dpLambda, &cout](int amount) -> int {
                if (amount >= iLcm) {
                    int toCompare = iLcm - largest + amount % largest;
                    return (amount - toCompare) / largest + dpLambda(toCompare);
                }
                if (amount < 0) return -1;
                if (dp[amount] != -2) return dp[amount];
                int minCoins = INT_MAX;
                for (int i = coins.size() - 1; i >=0; --i) {
                    int res = dpLambda(amount - coins[i]);
                    if (res != -1) {
                        minCoins = min(minCoins, res + 1);
                    }
                }
                dp[amount] = minCoins == INT_MAX ? -1 : minCoins;
                return dp[amount];
            };
            return dpLambda(amount);
        }
    
    private:
        long lcm(long a, long b) {
            long ret = a * b / lcd(a, b);
            if (ret < 0) {
                return LONG_MAX; // aproximately handle overflow case, since lcm is used to calculate how much elements you need for DP, and LONG_MAX guarantees it will never select the lcm, in case of overflow
            }
            return ret;
        }
    
        long lcd(long a, long b) {
            if (a < b) return lcd(b, a);
            if (b < 0) return lcd(a, -b);
            int mod = a % b;
            if (mod == 0) return b;
            return lcd(b, mod);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.