《剑指Offer》-60-n 个骰子的点数

打印出 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)的时间复杂度和6n²的空间复杂度

通常二维动态规划都可以优化为一维，这里也不例外，每一层其实都只依赖上一层，但是……考虑到覆盖的情况也不能一个数组就搞定了吧