打印出 n 个骰子所能扔出的所有点数的概率
思路
dp[i][j] 表示 i 个骰子，投出 j 的概率
而概率 = 点数出现的次数 / 总次数
而 i 个骰子掷出 j 的次数 = i - 1 个骰子掷出 j- 1 的次数 + i - 1 个骰子掷出 j -2 的次数 + … + i - 1 个骰子掷出 j -6 的次数，因为这个单独的骰子能掷出这 6 种结果，这里的 j - n 必须大于1
于是比如dp[2][3] = (dp[1][2]+dp[1][1])/6^2
vector<double> dicesProbability(int n) {
// dp[i][j]表示i个骰子掷出j的概率
vector<vector<double>> dp(n+1, vector<double>(6*n+1,0));
vector<double> res;
// 那么我们要得到的就是dp[n][n]到dp[n][6n]
// 如果转化为一个矩阵，那么整个右上角和左下角都是不要的
// 初始化
for (int i = 1; i <= 6; i++) dp[1][i] = 1.0 / pow(6,n);
for (int i = 2; i <= n; i++) {
for (int j = i; j <= 6*i; j++) {
int k = j-1;
while (k >= 1 && k>=j-6) {
dp[i][j] += dp[i - 1][k];
k--;
}
}
}
for (int i = n; i <= 6 * n; i++) res.push_back(dp[n][i]);
return res;
}
这是我想出最直观地做法，从 1 个骰子地所有情况开始向上递推，但是很明显套了三层循环，而且用了二维数组，时间和空间效率肯定都不好看，还好题目最大 n 也就 11，所以就接过来说还是看得下去的，但是肯定不能让面试官满意
这里的时间和空间复杂的其实是可以算出来的，3n(n+1)的时间复杂度和6n2的空间复杂度
通常二维动态规划都可以优化为一维，这里也不例外，每一层其实都只依赖上一层，但是……考虑到覆盖的情况也不能一个数组就搞定了吧