动态规划--骰子概率问题

力扣n个骰子的点数问题解法，使用动态规划解题思路含完整代码。

原题

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。 你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

1. 示例 1:
   • 输入: 1
   • 输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
2. 示例 2:
   • 输入: 2
   • 输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

解题思路

• 这是一个典型的动态规划问题，有点类似爬楼梯问题，在爬楼梯问题中我们一次可以移动1或2步，而这个骰子问题我们每次增加一个骰子则会增加六种可能。
• 输出结果使一个浮点型的切片，所有在动态规划的过程中我们可以建立一个二维切片来存储每次计算的结果，想要简化空间复杂度的话可以建立两个切片，一个last存储上一次计算的结果，一个temp存储当前结果，每次计算结束赋值last=temp并将temp清空即可。
• 当输入为1时，可以直接得出答案，即六个1/6。
• 假设输入为n，当我们已知dp(n-1)的情况下，当添加骰子的点数为c，前n-1个骰子的点数和应为x-c，方可组成点数和x。
• 反向思考，dp(n-1)中的每个结果，乘以1/6，都是dp(n)中往后六个元素的一部分。

代码实现

func dicesProbability(n int) []float64 {
    last := []float64{1.0 / 6, 1.0 / 6, 1.0 / 6, 1.0 / 6, 1.0 / 6, 1.0 / 6}
    temp := make([]float64, 11)

    for i := 1; i < n; i++ {
        for idx, val := range last {
            for count := 0; count < 6; count++ {
                current := idx + count
                temp[current] += val / 6
            }
        }
        last = temp
        temp = make([]float64, (i+2)*5+1)
    }
}

注意，比较麻烦的是，每次计算后，temp初始化需要计算切片的长度，避免赋值时索引超出切片长度报错。PS：还是JS香啊，哪里要想这么多。