文章目录

题目地址

力扣https://leetcode-/problems/nge-tou-zi-de-dian-shu-lcof/

代码

class Solution {public double[] dicesProbability(int n) {int[][] dp = new int[n+1][6 * n+1];for (int i = 1;i < 7; ++i) {dp[1][i] = 1;}for (int i = 2; i <= n ; ++i ) {for (int j = i; j <= 6 * i ; j++ ) {for (int cur = 1; cur <= j - i + 1&&cur<=6; cur++ ) {// d p[n][j]=\sum_{i=1}^{6} d p[n-1][j-i] 递推公式dp[i][j] += dp[i - 1][j - cur] ;}}}double total = Math.pow(6 , n);double[] res = new double[6*n-n+1];for (int i=n ; i<=6*n ;++i ) {res[i-n] = ((double)dp[n][i] ) / total;}return res;}}

递推公式

****

推导：

dp[1][1] = 1 dp[1][2] = 1 dp[1][3] = 1 dp[1][4] = 1 dp[1][5] = 1 dp[1][6] = 1

dp[2][2] = 1 dp[2][3] = 2 dp[2][4] = 3 dp[2][5] = 4 dp[2][6] = 5 dp[2][7] = 6

dp[2][8] = 5 dp[2][9] = 4 dp[2][10] = 3 dp[2][11] = 2 dp[2][12] = 1

dp[3][3] = 1 dp[3][4] = 3dp[3][5] = ？

dp[3][5]=dp[3-1][5-1]+dp[3-1][5-2]+dp[3-1][5-3]=3+2+1=6

空间优化

我们知道，每个阶段的状态都只和它前一阶段的状态有关，因此我们不需要用额外的一维来保存所有阶段。

用一维数组来保存一个阶段的状态，然后对下一个阶段可能出现的点数 jj 从大到小遍历，实现一个阶段到下一阶段的转换。

这里注意：第二层j循环需要倒着进行动态规划，正着的话数据会被覆盖（留给读者自行思考）

class Solution {public double[] dicesProbability(int n) {int[] dp = new int[6 * n+1];for (int i = 1;i < 7; ++i) {dp[i] = 1;}for (int i = 2; i <= n ; ++i ) {for (int j = 6 * i; j >= i ; j-- ) {dp[j] = 0;for (int cur = 1; cur <= j - i + 1&&cur<=6; cur++ ) {dp[j] += dp[j - cur] ;}}}double total = Math.pow(6 , n);double[] res = new double[6*n-n+1];for (int i=n ; i<=6*n ;++i ) {res[i-n] = ((double)dp[i] ) / total;}return res;}}

运行结果通过

上边的为优化后的，下面的是没优化过的