题目

image.png

思路

  • 思路一：暴力递归超时，当前求n个筛子能够抛出各个点数的概率，因此用recur(n,i)表示其概率，n表示可用点数，i表示所要求的值，每次递归中抛出的骰子有六种可能k(1,2,3,4,5,6)，因遍历recur(n-1,i-k) * 1/6，n-1表示使用了一个骰子，i-k表示剩余要求点数，递归的终止条件就是n==0&&i==0就可结束，其它都算失败结束
  • 思路二：备忘录，还是超时
  • 思路三：动态规划，就是递归的逆过程，应该属于背包类问题，定义dp[i][j]表示i个骰子中值为j的可能性，转移条件就是dp[i][j] += dp[i - 1][i -k]，也就是递归条件，初始化条件就是，当i=1时，也就是骰子个数为1时dp[1][j] = 1/6 | i\j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | | —- | —- | —- | —- | —- | —- | —- | —- | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 0 | 1/6 | 1/6 | 1/6 | 1/6 | 1/6 | 1/6 | | 2 | 0 | 0 | 1/61/6 | 1/61/62 | 1/61/63 | 1/61/64 | 1/61/65 | | 3 | 0 | 0 | 0 | 1/61/61/6 | … | | | | 4 | 0 | 0 | 0 | 0 | 1/61/61/61/6 | … | | | 5 | 0 | 0 | 0 | 0 | 0 | 1/61/61/61/61/6 | …. | | 6 | 0 | 0 | 0 | 0 | 0 | 0 | 1/61/61/61/61/6*1/6 |

  • 思路四：优化动态规划数组，主要是画图

    代码

    1.   //1. 暴力递归超时，别直接用0.16667，要用1/6d，不然哭唧唧
    2.   public double[] dicesProbability(int n) {
    3.       double[] res = new double[5 * n + 1];
    4.       for (int i = n; i <= 6 * n; i++) {
    5.           res[i - n] = recur(n, i);
    6.       }
    7.       return res;
    8.   }
    10.   public double recur(int n, int target) {
    11.       if (n == 0 && target == 0) return 1;
    12.       if (n <= 0 || target < 0) return 0;
    13.       double res = 0;
    14.       for (int i = 1; i <= 6; i++) {
    15.           if (target >= i)  {
    16.               res += recur(n - 1, target - i) * 1/6d;
    17.           }
    18.       }
    19.       return res;
    20.   }
    22.   //2.备忘录 还是超时
    23.   double[][] dp;
    24.   public double[] dicesProbability(int n) {
    25.       double[] res = new double[5 * n + 1];
    26.       dp = new double[n + 1][6 * n + 1];
    27.       for (int i = n; i <= 6 * n; i++) {
    28.           res[i - n] = recur(n, i);
    29.       }
    30.       return res;
    31.   }
    33.   public double recur(int n, int target) {
    34.       if (n == 0 && target == 0) return 1;
    35.       if (n <= 0 || target < 0) return 0;
    36.       if (dp[n][target] != 0) return dp[n][target];
    37.       double res = 0;
    38.       for (int i = 1; i <= 6; i++) {
    39.           if (target >= i)  {
    40.               res += recur(n - 1, target - i) * 1/6d;
    41.           }
    42.       }
    43.       dp[n][target] = res;
    44.       return res;
    45.   }
    47.   //3.动态规划
    48.   public double[] dicesProbability(int n) {
    49.       //dp[i][j]表示i个筛子，值为j时的概率
    50.       double[][] dp = new double[n + 1][6 * n + 1];
    51.       double[] res = new double[5 * n + 1];
    52.       for (int j = 1; j <= 6; j++) {
    53.           dp[1][j] =  1/6d;
    54.       }
    55.       for (int i = 1; i <= n; i++) {
    56.           for (int j = i; j <= 6 * i; j++) {
    57.               for (int k = 1; k <= 6; k++) {
    58.                   if (j >= k) {
    59.                       dp[i][j] += dp[i - 1][j - k] * 1 /6d;
    60.                   }
    61.               }
    62.               if (i == n) {
    63.                   res[j - n] = dp[i][j];
    64.               }
    65.           }
    66.       }
    67.       return res;
    68.   }
    70.   //4. 优化dp数组，由于每次只使用前一行的数据，所以可以优化为一维，但是要有额外一维数组保存新值
    71.   public double[] dicesProbability(int n) {
    72.       //dp[j]筛子为i值为j时的概率
    73.       double[] dp = new double[6 * n + 1];
    74.       double[] updateDp = new double[6 * n + 1];
    75.       double[] res = new double[5 * n + 1];
    76.       for (int j = 1; j <= 6; j++) {
    77.           dp[j] =  1/6d;
    78.           res[j - 1] = 1/6d;
    79.       }
    80.       for (int i = 2; i <= n; i++) {
    81.           for (int j = i; j <= 6 * i; j++) {
    82.               double updateValue = 0;
    83.               for (int k = 1; k <= 6; k++) {
    84.                   //因为有i个筛子，所以点数至少大于等于i
    85.                   if (j - k + 1 >= i) updateValue += dp[j - k] * 1/6d;
    86.               }
    87.               updateDp[j] = updateValue;
    88.               if (i == n) res[j - n] = updateDp[j];
    89.           }
    90.           double[] t = updateDp;
    91.           updateDp =  dp;
    92.           dp = t;
    93.       }
    94.       return res;
    95.   }

    n个骰子的点数