题目描述

略

样例

略

算法1

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

不难知道n个骰子时,和为m可以看做n-1骰子的点确定之后与最后一个的点数求和
所以有 a[n][m]=a[n-1][m-1]+…+a[n-1][m-6]
再注意边界情况即可

C++ 代码

class Solution {
public:
    vector<int> numberOfDice(int n) {
        vector< vector<int> >ans(n+1, vector<int>(6*n+2,0));
        ans[1]={0,1,1,1,1,1,1,0};
        for(int i=1;i<=n;i++){
            for(int j=i;j<6*i+1;j++){
                for(int k=1;j-k>0&&k<=6;k++){
                    ans[i][j]+=ans[i-1][j-k];
                }
            }
        }
        vector<int> c(ans[n].begin()+n,ans[n].begin()+6*n+1);
        return c;
    }
};