← all categories

Knapsack Unbounded 980f153e

Unbounded knapsack / coin-change count-of-ways (each item usable any number of times), 1D rolling array. Capacity loop goes low-to-high — the opposite direction from knapsack-01.h, which is exactly why that direction matters.

Time: O(n \cdot target). tested

content/dp/knapsack-unbounded.h

ll coinWays(vector<ll> &coins, ll target, ll MOD) {
    vector<ll> dp(target + 1, 0);
    dp[0] = 1;
    for (ll c : coins)
        for (ll w = c; w <= target; w++) dp[w] = (dp[w] + dp[w - c]) % MOD;
    return dp[target];
}