题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：指数级别的

C++ 代码

class Solution {
public:
    vector<int> numberOfDice(int n) {
        //状态的含义是什么的
        //顺序是什么
        vector<int>res;
        for(int i = n; i <= n * 6; i ++) res.push_back(dfs(n,i));
        return res;
    }
    int dfs(int n, int sum){
        if(sum < 0) return 0;
        if( n == 0) return !sum;
        int res;
        for(int i = 1; i <= 6; ++i){
            res += dfs(n-1,sum-i)
        }
    }
};

算法2

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

分组背包问题

• 状态表示f[i][j]：表示前i次总和是j的方案数
• 状态转化：f[i][j] += f[i-1][i - k]
• 边界条件：

C++ 代码

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