[完全背包]leetcode2240：买钢笔和铅笔的方案数(medium)

题目：

题解：

代码如下：

using LL = long long;
class Solution {
public:
    long long waysToBuyPensPencils(int n, int c1, int c2) {
        return dp2(n,c1,c2);
    }

    LL dp2(int n,int c1,int c2)
    {
        vector f(n+1,1);
        for(int v:{c1,c2})
            for(int j=v;j<=n;++j)
                f[j]+=f[j-v];
        return f[n];
    }
    // 二维dp
    LL dp1(int n,int c1,int c2)
    {
        vector> f(3,vector(n+1,0));
        // 从0件物品中选，总体积不超过j得方案数为1
        for(int j=0;j<=n;++j)f[0][j]=1;
        // 开始进行状态转移，求的是组合数，先遍历物品，再遍历背包
        for(int i=1;i<=2;++i)
            for(int j=0;j<=n;++j)
            {
                f[i][j]+=f[i-1][j];
                int c=i==1?c1:c2;
                if(j>=c)f[i][j]+=f[i][j-c];
            }
        return f[2][n];
    }
};