动态规划,第n次投掷骰子,点数为k出现的次数为第n-1次投掷骰子点数为k-1,k-2,k-3,k-4,k-5,k-6的和
class Solution {
public int[] numberOfDice(int n) {
int[] pre=new int[6*n+1];
int[] cur=new int[6*n+1];
//cur表示当前的投掷情况,pre表示上一次的投掷情况
for(int i=1;i<=6;i++){
//先给第一次赋值,也就是动归的初始状态
cur[i]=1;
}
for(int N=2;N<=n;N++){
//cur和pre的交替
int[] temp=cur;
cur=pre;
pre=temp;
for(int k=1;k<=6*N;k++){
//需要将上一次的cur清理干净
cur[k]=0;
//当k在[N,6N]之间时,需要累积pre状态下N-1,N-2,N-3,N-4.N-5.N-6的次数和
if(k>=N){
for(int x=1;x<=6&&x<=k;x++){
cur[k]+=pre[k-x];
}
}
}
}
int[] rrr=new int[5*n+1];
for(int i=n;i<cur.length;i++){
rrr[i-n]=cur[i];
}
return rrr;
}
}