60. n 个骰子的点数

题目链接

Lintcode

题目描述

把 n 个骰子扔在地上，求点数和为 s 的概率。

解题思路

动态规划

使用一个二维数组 dp 存储点数出现的次数，其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。

空间复杂度：O(N²)

// java
public List<map.entry> dicesSum(int n) {
    final int face = 6;
    final int pointNum = face * n;
    long[][] dp = new long[n + 1][pointNum + 1];

    for (int i = 1; i <= face;="" i++)="" dp[1][i]="1;" for="" (int="" i="2;" <="n;" j="i;" j++)="" *="" 使用="" 个骰子最小点数为="" k="1;" &&="" k++)="" dp[i][j]="" +="dp[i" -="" 1][j="" k];="" final="" double="" totalnum="Math.pow(6," n);="" list<map.entry> ret = new ArrayList<>();
    for (int i = n; i <= pointnum;="" i++)="" ret.add(new="" abstractmap.simpleentry(i, dp[n][i] / totalNum));

    return ret;
}
</map.entry

动态规划 + 旋转数组

空间复杂度：O(N)

// java
public List<map.entry> dicesSum(int n) {
    final int face = 6;
    final int pointNum = face * n;
    long[][] dp = new long[2][pointNum + 1];

    for (int i = 1; i <= face;="" i++)="" dp[0][i]="1;" int="" flag="1;" *="" 旋转标记="" for="" (int="" i="2;" <="n;" i++,="" -="" flag)="" {="" j="0;" j++)="" dp[flag][j]="0;" 旋转数组清零="" k="1;" &&="" k++)="" +="dp[1" flag][j="" k];="" }="" final="" double="" totalnum="Math.pow(6," n);="" list<map.entry> ret = new ArrayList<>();
    for (int i = n; i <= pointnum;="" i++)="" ret.add(new="" abstractmap.simpleentry(i, dp[1 - flag][i] / totalNum));

    return ret;
}
</map.entry