考虑用动归,数组dp[i][j]表示用i个骰子扔出和为j的可能数,因为第i个骰子可能扔出1-6的点数,则dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4]+dp[i-1][j-5]+dp[i-1][j-6],由于我们只需要用到最后一次的结果,因此为了节省空间可以使用滚动数组,将二维dp数组变为一维。
class Solution {
public:
vector<int> numberOfDice(int n) {
vector<int>ans;
int f[6*n+1]={0};
f[0]=1;
for(int i=1;i<=n;i++){
for(int j=6*i;j>=0;j--){
f[j]=0;
for(int k=1;k<=6;k++){
if(j>=k)f[j]+=f[j-k];
}
}
}
for(int i=n;i<=6*n;i++){
ans.push_back(f[i]);
}
return ans;
}
};