记忆化搜索

qnmd dp，ms YYDS！

class Solution {
public:
    vector<vector<int>> f;

    vector<int> numberOfDice(int n) {
        f = vector<vector<int>>(n + 1, vector<int>(6 * n + 1, -1));
        vector<int> res;
        for (int i = n; i <= 6 * n; i++) {
            res.push_back(dfs(n, i));
        }
        return res;
    }

    int dfs(int n, int sum) {
        if (sum < 0) return 0;
        if (f[n][sum] != -1) return f[n][sum];
        if (!n) return !sum;
        int res = 0;
        for (int i = 1; i <= 6; i++) {
            res += dfs(n - 1, sum - i);
        }
        return f[n][sum] = res;
    }
};

DP

class Solution {
public:
    vector<int> numberOfDice(int n) {
        vector<vector<int>> f(n + 1, vector<int>(6 * n + 1));
        f[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= 6 * n; j++) {
                for (int k = 1; k <= min(6, j); k++) {
                    f[i][j] += f[i - 1][j - k];
                }
            }
        }

        vector<int> res;
        for (int i = n; i <= 6 * n; i++) {
            res.push_back(f[n][i]);
        }

        return res;
    }
};