剑指 Offer 60. n个骰子的点数

• 确定问题解的表达式：可将f(n, s) 表示n个骰子点数为s的排列情况总数

• 确定状态转移方程：n个骰子点数和为s的种类数只与n-1个骰子的和有关。因为一个骰子有六个点数，那么第n个骰子可能出现1到6的点数。所以第n个骰子点数为1的话，f(n,s)=f(n-1,s-1)，当第n个骰子点数为2的话，f(n,s)=f(n-1,s-2)，…，依次类推。在n-1个骰子的基础上，再增加一个骰子出现点数和为s的结果只有这6种情况！那么有：f(n,s)=f(n-1,s-1)+f(n-1,s-2)+f(n-1,s-3)+f(n-1,s-4)+f(n-1,s-5)+f(n-1,s-6)

上面就是状态转移方程，已知初始阶段的解为：当n=1时, f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1

class Solution {
    
public:
    vector<double> dicesProbability(int n) {
    
        vector<vector<int>> dp(n + 1, vector<int>(6 * n + 1, 0));
        for(int j = 1; j <= 6; ++j){
    
            dp[1][j] = 1;
        }
        // i个色子，进入循环则表示至少2个色子
        for(int i = 2; i <= n; i++){
    
            // i个色子掷出j，j表示当前的总点数，i个色子点数范围是[i, 6*i]
            for(int j = i; j <= 6*i; ++j){
    
                // k表示最后一个色子的点数
                for(int k = 1; k <= 6; ++k){
    
                    if(k >= j){
    
                        // 最后一个点数的色子不能超过总点数，也不能相等
                        break;
                    }
                    if(j-k < (i-1) || j-k > 6*(i-1)){
    
                    	// 如果i-1个色子得到的点数j-k不在[i-1,6*(i-1)]范围内，则当前色子点数k不合法，继续下一轮循环
                        continue;
                    }
                    // dp[i-1][j-k]表示最后一个色子的点数为k，前面i-1色子的点数为j-k
                    dp[i][j] += dp[i-1][j-k];
                }
            }
        }

        vector<double> ans;
        int num = pow(6, n); // 每个色子有6中可能，总频数为6^n
        for(int j = n; j <= 6*n; ++j){
    
            ans.push_back(dp[n][j] * 1.0 / num);
        }
        return ans;
    }
};

n=8时，dp数组如下所示：

0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0
0       1       1       1       1       1       1       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0
0       0       1       2       3       4       5       6       5       4       3       2       1       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0
0       0       0       1       3       6      10      15      21      25      27      27      25      21      15      10       6       3       1       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0
0       0       0       0       1       4      10      20      35      56      80     104     125     140     146     140     125     104      80      56      35      20      10       4       1       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0
0       0       0       0       0       1       5      15      35      70     126     205     305     420     540     651     735     780     780     735     651     540     420     305     205     126      70      35      15       5       1       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0       0
0       0       0       0       0       0       1       6      21      56     126     252     456     756    1161    1666    2247    2856    3431    3906    4221    4332    4221    3906    3431    2856    2247    1666    1161     756     456     252     126      56      21       6       1       0       0       0       0       0       0       0       0       0       0       0       0
0       0       0       0       0       0       0       1       7      28      84     210     462     917    1667    2807    4417    6538    9142   12117   15267   18327   20993   22967   24017   24017   22967   20993   18327   15267   12117    9142    6538    4417    2807    1667     917     462     210      84      28       7       1       0       0       0       0       0       0
0       0       0       0       0       0       0       0       1       8      36     120     330     792    1708    3368    6147   10480   16808   25488   36688   50288   65808   82384   98813  113688  125588  133288  135954  133288  125588  113688   98813   82384   65808   50288   36688   25488   16808   10480    6147    3368    1708     792     330     120      36       8       1

n个色子可以掷出的点数为[n,6*n]，故第n行填写的是[n,n]->[n,6*n]