题目描述
将一个骰子投掷 n 次,获得的总点数为 s,s 的可能范围为 n∼6n。
掷出某一点数,可能有多种掷法,例如投掷 2 次,掷出 3 点,共有 [1,2],[2,1] 两种掷法。
请求出投掷 n 次,掷出 n∼6n 点分别有多少种掷法。
样例
样例1
输入:n=1
输出:[1, 1, 1, 1, 1, 1]
解释:投掷1次,可能出现的点数为1-6,共计6种。每种点数都只有1种掷法。所以输出[1, 1, 1, 1, 1, 1]。
样例2
输入:n=2
输出:[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]
解释:投掷2次,可能出现的点数为2-12,共计11种。每种点数可能掷法数目分别为1,2,3,4,5,6,5,4,3,2,1。
所以输出[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]。
算法1
(暴力枚举) $O(n^2)$
C++ 代码
class Solution {
public:
vector<int> numberOfDice(int n) {
//状态标识 投了i次,和为j的方案数,和的取值为 i - 6i
vector<vector<int>> f(n + 1, vector<int>(6 * n + 1)); //为了好处理边界问题,多增加一个维度
f[0][0] = 1;
for(int i = 1; i <= n; ++i){ //第i次
for(int j = i; j <= 6 * i; ++j){ //和为j
for(int k = 1; k <= 6 && k <= 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]); //投n次,和最小为n
return res;
}
};