本文共 2349 字，大约阅读时间需要 7 分钟。

题目描述：

将一个骰子投掷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]。

分析：

方法一：DFS

采用自顶而下的dfs。dfs（n，i）表示掷n次骰子得到总点数为i所有可能的掷法。边界情况，s不能为负，n为0时，s也要为0才能算一次正确的掷法。然后就是枚举每次掷的点数，将n-1，s-i再考虑下次的掷法。这种方法复杂度极高，可能达到指数级别，因此在n=9时便超时了。

class Solution {public:    vector
   
     numberOfDice(int n) {        vector
    
      ans;        for(int i = n;i <= 6 * n;i++)   ans.push_back(dfs(n,i));        return ans;    }    int dfs(int n,int s){        if(s < 0) return 0;        if(n == 0)  return !s;        int res = 0;        for(int i = 1;i <= 6;i++)   res += dfs(n - 1,s - i);        return res;    }};
    
   

方法二：记忆化搜索

dfs超时的根源在于重复计算，而记忆化搜索则可帮助消除重复计算。这种重复计算不仅在一次递归中，比如dfs（6,10），第一次掷1，第二次掷2得到dfs（4,7）；倘若第一次掷2，第二次掷1同样得到dfs（4,7），这种情况dfs（4，7）就重复的被计算了。在多次递归中也会有这样类似的重复调用，所以我们保存下已经计算过的状态即可。由还需要掷的次数n已经还剩下的总和s可唯一确定一种状态，这种状态继续往下计算得到的解是相同的，所以当某种状态已经被计算过了，直接返回即可。

注意：这里st数组初值都设置的是-1，如果设置为0，则在n=10的情况下就超时了。原因是存在大量行不通的方案，这种方案对最终次数统计的贡献正是0。

class Solution {public:    int st[100][600];    vector
   
     numberOfDice(int n) {        vector
    
      ans;        for(int i = 0;i < 100;i++)            for(int j = 0;j < 600;j++)                st[i][j] = -1;        for(int i = n;i <= 6 * n;i++)   ans.push_back(dfs(n,i));        return ans;    }    int dfs(int n,int s){        if(s < 0) return 0;        if(n == 0)  return !s;        if(st[n][s] != -1)   return st[n][s];        int res = 0;        for(int i = 1;i <= 6;i++)   res += dfs(n - 1,s - i);        st[n][s] = res;        return res;    }};
    
   

方法三：动态规划

也可以采用动态规划自下而上的进行计算，之前dfs（n，s）的本质是还要掷n次，这n次的总和为s。现在设f[i][j]为掷了i次总和为j的方案数。则f[i][j]可由f[i-1][j-k]，k从1到min（6，j），转移过来。即第i次掷的点数为1到k这么多种方案数的总和。

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

转载地址：http://jxkyk.baihongyu.com/