算法1

(动态规划) $O(n^2)$

dp[i][j] 表示i个骰子和为j的所有可能数量

C++ 代码

class Solution {
public:
    vector<int> numberOfDice(int n) {
        //dp[i][j]: 
        vector<vector<int>> dp(n + 1, vector<int> (6 * n + 1, 0));
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= 6 * n; ++j) {
                dp[i][j] += dp[i][j - 1] + dp[i - 1][j - 1];
                if (j - 7 >= 0)
                    dp[i][j] -= dp[i - 1][j - 1 - 6];
            }
        }
        vector<int> ans;
        for (int i = n; i <= 6 * n; ++i) {
            ans.push_back(dp[n][i]);
        }
        return ans;
    }
};