[完全背包]leetcode518：零钱兑换 II(medium)

题目：

题解：

思路：来自AcWing 900. 整数划分的完全背包解法。

代码如下：

const int M = 310, N = 5010;
// 状态f[i][j]表示从前i种物品中选且总体积恰好为j的选法的方案数
int f[M][N];
class Solution {
public:
    // 完全背包解法：给定m种物品的体积，每种物品可使用无限次，求恰好装满体积n的所有方案数
    int change(int n, vector& v) {
        // 由于求的是恰好装满体积n，所以无效值设为0，即刚开始时恰好装满体积j的方案数为0
        memset(f,0,sizeof f);
        int m=v.size();
        // 一个物品都不选，且总体积为0的方案数只有1个
        for(int i=0;i<=m;++i)f[i][0]=1;
        // 开始进行状态转移
        for(int i=1;i<=m;++i)
            for(int j=0;j<=n;++j)
            {
                f[i][j]=f[i-1][j];
                // 第i个物品选的个数，是由前i-1个物品的方案数累加得到的
                // f[i][j-i]=max(f[i-1][j-k*i])，其中k>=1；所以只用f[i][j-i]就可以推出f[i][j]的所有右子集了
                if(j>=v[i-1])f[i][j]+=f[i][j-v[i-1]];
            }
        // 最终结果为从m个物品中选，且总体积恰好为n的所有方案数
        return f[m][n];
    }
};