518. Coin Change 2

经典背包问题
从小往大推就不会有事

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int ans[5005];
        memset(ans, 0, sizeof(ans));
        ans[0] = 1;
        for (int i = 0; i < coins.size(); i++)
            for (int j = 0; j < amount; j++) {
                if (j + coins[i] > amount)
                    break;
                ans[j + coins[i]] += ans[j];
            }
        return ans[amount];
    }
};