1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <iostream>
#include <vector>

class Solution {
public:
    int change(int amount, std::vector<int>& coins) {
        std::vector<long long> dp(amount + 1);
        dp[0] = 1;
        for (int c : coins) {
            for (int i = c; i <= amount; ++i) {
                dp[i] += dp[i - c];
                dp[i] &= 0x7fff'ffff;
            }
        }
        return dp.back();
    }
};