滚动数组

class Solution {
public:
    vector<int> numberOfDice(int n) {
        vector<vector<int>> f(2,vector<int>(n*6+1));
        f[0][0]=1;
        int a=1;
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=6*i;j++) {
                f[a&1][j]=0;  // 必须有这一步 将该位置的值清零 上一步结果干扰计数准确
                for(int k=1;k<=min(6,j);k++) {
                    if(j-k<i-1) continue; // i-1步所掷出的点数至少为i-1 
                    else f[a&1][j]+=f[a^1][j-k];
                }
            }
            a^=1;
        }
        vector<int> res;
        for(int i=n;i<=6*n;i++) res.push_back(f[a^1][i]);
        return res;
    }
};

分组背包

vector<int> numberOfDice(int n) {
        vector<int> f(6*n+1);
        f[0]=1;
        for(int i=1;i<=n;i++) {
            for(int j=i*6;j>=0;j--) {
                f[j]=0;
                for(int k=1;k<=min(j,6);k++) {
                    if(j-k<i-1) continue;
                    else f[j]+=f[j-k];
                }
            }
        }
        vector<int> res;
        for(int i=n;i<=n*6;i++) res.push_back(f[i]);
        return res;
    }