如何使用动态规划找到最大概率？
How do I find the maximum probability using dynamic programming?
为了更好地理解这个问题，您可以查看：-
1) https://math.stackexchange.com/questions/3100336/how-to-calculate-the-probability-in-this-case
约翰正在和一个magician.In玩游戏，最初有'N'个相同的盒子在他面前，其中一个盒子里装着一颗魔法药丸——吃了这颗药丸后，他就变成了永生.
他必须确定哪个盒子里装有药丸。他最多可以执行 'M' 个动作。在每一步中，他可能会执行以下操作之一：
1)
在他面前均匀地随机选择一个盒子，猜猜这个盒子里装的是药丸。如果猜对了，游戏结束，他得到药丸。否则，在这个猜测之后，魔术师在他面前添加了 K 个空盒子，约翰无法确定添加了哪些盒子；他猜到的那个方块也留在了他的面前，他在后面的走法中也分不清这个方块和其他的方块。
2) 选择一个数字 X，使 X 是 K 的正倍数，但严格小于 John 前面的当前框数。然后魔术师取出 X 个空盒子。当然，如果当前的箱子数量≤K，John一定不能执行此步。
如果约翰表现最佳，他得到药丸的最大概率是多少？ 'N' 总是小于 'K'.
示例：- 设 M=3，因此允许 3 次移动。 K=20,N=3.
在他的第一步中，约翰选择了一个盒子，概率为 x = 1/3 ，（已添加 20 个盒子（20+3==23）然后在第二步中，他再次选择了一个盒子， with probability 这次，y=1/23*(2/3)。这里，2/3表示第一步失败的概率。
在第三步中，他以概率做同样的事情，z = 1/43*(22/23)*(2/3)。
所以总概率是=x+y+z=l1
比方说，在上面的例子中，在第二步，他选择移除20个盒子，什么都不做，那么新的最终概率是= 1/3+0（第二步什么都不做！） + 2/3*(1/3)=l2。现在，因为 l2 > l1 ，所以 'l2' 就是我们问题的答案。
基本上，我们必须确定哪个动作序列产生最大概率？另外，
P（获胜）=P（游戏以第 1 步结束）+P（游戏以第 2 步结束）+P（游戏以第 3 步结束）=（1/3）+0+（2/3） *(1/3) =5/9
给定N,K,M我们如何找出最大概率？
我们必须应用动态规划吗？
设p(N,K,M) 是 John 最佳发挥的概率。我们有以下递推关系：
- p(N, K, 0) = 0
- 如果没有剩余的步数，那么他就输了。
- 如果 M > 0 且 N < X，则 p(N, K, M) = 1 /N + (N−1)/N · p(N+ K, K, M−1)
- 如果至少还剩一步，并且选项#2不被允许，那么他获胜的概率就是他这一轮猜对的概率加上他这一轮猜错的概率但是他在后面的回合中获胜。
- 如果 M > 0 且 N ≥ X，则 p(N, K, M) 是这两个中的较大者：
- 1/N + ( N−1)/N·p(N+K, K, M−1)
- 如果他选择选项#1，那么这与他被迫选择选项#1 的情况相同。
- p(N % K, K, M−1), 其中 '%' 是 "remainder" 或 "modulus" 运算符
- 如果他选择#2，那么这一步他肯定赢不了，所以他赢的概率等于他后面回合赢的概率。
- 注意，我们只需要考虑N % K，因为他肯定要选择的最大值X 他被允许了。让盒子池保持不必要的大从来没有任何好处。
动态编程，或递归加记忆，非常适合这种情况；可以直接套用上面的递推关系
请注意 K 永远不会改变，因此您不需要数组维度；并且 N 仅通过添加或减去 K 的整数倍来更改，因此最好使用数组索引 n 这样 N = (N0 % K) + nK.
此外，请注意 M 每轮减少 1，因此如果您使用动态规划方法并且您只想要最终概率，那么您不需要不需要为 M 的所有值保留概率；相反，当为 M 的给定值构建数组时，您只需要保留 M−1.
的数组
为了更好地理解这个问题，您可以查看：-
1) https://math.stackexchange.com/questions/3100336/how-to-calculate-the-probability-in-this-case
约翰正在和一个magician.In玩游戏，最初有'N'个相同的盒子在他面前，其中一个盒子里装着一颗魔法药丸——吃了这颗药丸后，他就变成了永生.
他必须确定哪个盒子里装有药丸。他最多可以执行 'M' 个动作。在每一步中，他可能会执行以下操作之一：
1)
在他面前均匀地随机选择一个盒子，猜猜这个盒子里装的是药丸。如果猜对了，游戏结束，他得到药丸。否则，在这个猜测之后，魔术师在他面前添加了 K 个空盒子，约翰无法确定添加了哪些盒子；他猜到的那个方块也留在了他的面前，他在后面的走法中也分不清这个方块和其他的方块。
2) 选择一个数字 X，使 X 是 K 的正倍数，但严格小于 John 前面的当前框数。然后魔术师取出 X 个空盒子。当然，如果当前的箱子数量≤K，John一定不能执行此步。
如果约翰表现最佳，他得到药丸的最大概率是多少？ 'N' 总是小于 'K'.
示例：- 设 M=3，因此允许 3 次移动。 K=20,N=3.
在他的第一步中，约翰选择了一个盒子，概率为 x = 1/3 ，（已添加 20 个盒子（20+3==23）然后在第二步中，他再次选择了一个盒子， with probability 这次，y=1/23*(2/3)。这里，2/3表示第一步失败的概率。
在第三步中，他以概率做同样的事情，z = 1/43*(22/23)*(2/3)。
所以总概率是=x+y+z=l1
比方说，在上面的例子中，在第二步，他选择移除20个盒子，什么都不做，那么新的最终概率是= 1/3+0（第二步什么都不做！） + 2/3*(1/3)=l2。现在，因为 l2 > l1 ，所以 'l2' 就是我们问题的答案。
基本上，我们必须确定哪个动作序列产生最大概率？另外，
P（获胜）=P（游戏以第 1 步结束）+P（游戏以第 2 步结束）+P（游戏以第 3 步结束）=（1/3）+0+（2/3） *(1/3) =5/9
给定N,K,M我们如何找出最大概率？ 我们必须应用动态规划吗？
设p(N,K,M) 是 John 最佳发挥的概率。我们有以下递推关系：
- p(N, K, 0) = 0
- 如果没有剩余的步数，那么他就输了。
- 如果 M > 0 且 N < X，则 p(N, K, M) = 1 /N + (N−1)/N · p(N+ K, K, M−1)
- 如果至少还剩一步，并且选项#2不被允许，那么他获胜的概率就是他这一轮猜对的概率加上他这一轮猜错的概率但是他在后面的回合中获胜。
- 如果 M > 0 且 N ≥ X，则 p(N, K, M) 是这两个中的较大者：
- 1/N + ( N−1)/N·p(N+K, K, M−1)
- 如果他选择选项#1，那么这与他被迫选择选项#1 的情况相同。
- p(N % K, K, M−1), 其中 '%' 是 "remainder" 或 "modulus" 运算符
- 如果他选择#2，那么这一步他肯定赢不了，所以他赢的概率等于他后面回合赢的概率。
- 注意，我们只需要考虑N % K，因为他肯定要选择的最大值X 他被允许了。让盒子池保持不必要的大从来没有任何好处。
- 1/N + ( N−1)/N·p(N+K, K, M−1)
动态编程，或递归加记忆，非常适合这种情况；可以直接套用上面的递推关系
请注意 K 永远不会改变，因此您不需要数组维度；并且 N 仅通过添加或减去 K 的整数倍来更改，因此最好使用数组索引 n 这样 N = (N0 % K) + nK.
此外，请注意 M 每轮减少 1，因此如果您使用动态规划方法并且您只想要最终概率，那么您不需要不需要为 M 的所有值保留概率；相反，当为 M 的给定值构建数组时，您只需要保留 M−1.
的数组