问题

求N个色子每个可能加和的概率

输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

算法：多重背包DP

容易看出这道题的本质是多重背包：总的加和方案数为$6^N$, 只要求出每个可能加和的方案数即可。而把和看作体积，就能转化为多重背包了：N个色子就是N个物品，每个色子可以取1-6的值，就是物品的数量。

定义f[i][j]为i个色子和为j的方案数
可写出状态转移方程：
$f[i][j] = f[i-1][j-k]$

但是有两点需要跟多重背包区别：
1. 每个色子至少取1，所以状态转移时和（体积）至少从i-1转（i为当前色子数）
2. 求种类数，必须先将当前答案清空（空间优化才需要这样做）

复杂度

时间：$O(NM)$
空间：$O(M)$

代码

class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<int> f(70);
        for(int j = 1; j <= 6; j ++){
            f[j] = 1;
        }

        for(int i = 2; i <= n; i ++){
            for(int j = 6 * i; j >= i; j --){
                f[j] = 0; // 与多重背包的差别：这里是求种类数而不是求最大值，必须将答案先清空
                for(int k = 1; k <= 6; k ++){
                    if(j-k < i-1) break; // 与多重背包的差别：每个色子至少为1，多重背包每个物品可以不拿
                    f[j] += f[j-k];
                }

            }
        }

        vector<double> res;
        int all = pow(6, n);
        for(int i = n; i <= 6*n; i ++){
            res.push_back(f[i] * 1.0 / all);
        }

        return res;
    }
};