题目描述
骰子的点数
样例
输入:n=1
输出:[1, 1, 1, 1, 1, 1]
解释:投掷1次,可能出现的点数为1-6,共计6种。每种点数都只有1种掷法。所以输出[1, 1, 1, 1, 1, 1]。
输入: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
(递归方法)
每次把掷的次数分为1次和n-1次,进行递归处理,1次的分为6中可能[1,2,3,4,5,6],剩下的n-1次在向下递归,直到递归的n等于1了,这是递归终止条件,递归不好解释,直接看下面的代码吧,就是无敌递归。
抄答案的,来自剑指offer
参考文献
剑指offer
C++ 代码
void fillAry(vector<int> &ans,int n,int sum,int startIndex)
{
if(n == 1)
ans[sum - startIndex]++;
else
{
for(int i = 1; i <= 6; ++i)
fillAry(ans,n-1,sum + i,startIndex);
}
}
vector<int> numberOfDice(int n) {
if(n == 1)
return vector<int>(6,1);
vector<int> ans(6*n - n + 1,0);
for(int i = 1; i <= 6; ++i)
fillAry(ans,n,i,n);
return ans;
}
算法2
(算是一种dp)
这里很巧妙的,举个例子,当掷一次色子,六个数都会出现一次,因为就都是1,再掷一次色子,那么第二次筛子出现6个数的次数也是一样的,但是加上第一次的6个数,导致总体出现n的次数是,n-1,n-2,n-3,n-4,n-5,n-6的,因为本次色子个数可能为1,2,3,4,5,6加上上次的n-1,n-2,n-3,n-4,n-5,n-6,都是n,所以可以这样不断地递推,最后就能得到最后地答案。
参考文献
剑指oofer
C++ 代码
vector<int> numberOfDice(int n)
{
vector<vector<int>> ans(2,vector<int>(6*n+1,0));
int flag = 0;
for(int i = 1; i <= 6; ++i)
ans[flag][i] = 1;
for(int k = 2; k <= n; ++k)
{
for(int i = 0; i < k; ++i)
ans[1-flag][i] = 0;
for(int i = k; i <= 6 * k; ++i)
{
ans[1-flag][i] = 0;
for(int j = 1; j <= i && j <= 6; ++j)
ans[1-flag][i] += ans[flag][i-j];
}
flag = 1 - flag;
}
return {ans[flag].begin()+n,ans[flag].end()};
}
算法3
(dp实现)
具体详情看下述代码吧,就是dp实现。
参考文献
剑指oofer
C++ 代码
vector<int> numberOfDice(int n)
{
vector<vector<int>> ans(n+1,vector<int>(6*n+1,0));
for(int i = 1; i <= 6; ++i)
ans[1][i] = 1;
for(int k = 2; k <= n; ++k)
{
for(int i = k; i <= 6 * k; ++i)
{
for(int j = 1; j <= i && j <= 6; ++j)
ans[k][i] += ans[k-1][i-j];
}
}
return {ans[n].begin()+n,ans[n].end()};
}