如何在 O(n) 中使用 DP 计算预期转数？
How to calculate expected number of turns using DP in O(n)?
单人棋盘游戏。该板由一排 n 个单元格组成，从左到右编号为 1 到 n
正确的。单元格“j”包含一个正整数 cj。
规则是这样的：
- 您从最左边的单元格开始。
- 在每一轮中，您掷出一个公平的 6 面骰子，结果数字为 A。你
向前移动 A × cj 个单元格，其中 j 是您所在单元格的索引
上。
- 退出棋盘即为赢，即指数 j > n 为赢。
例如，考虑大小为 n=10 的棋盘
首先，您位于第一个值为 c1 = 2 的单元格中。在第一轮中，您掷骰子
并获得一个值 1，所以你向前移动 2 个单元格。然后在下一次掷骰中，您在单元格 3 上掷出 5
（c3 = 4），所以你向前移动 20 个单元格会让你退出棋盘。你赢了！！你拿了 2
轮到赢了。
如何使用运行时间为 (n) 的动态规划算法计算上述游戏获胜所需的预期回合数？
您要查找的递归关系是：
E[j] = 0 (if j > n)
E[j] = 1 + 1/6 * sum_k(E[j + k * c_j]) (otherwise, for k \in 1..6)
对于每个单元格，计算平均获胜的回合数。
对于 k>=n 的单元格[k]，这是 0。
对于其他k处获胜的次数为1加上回合的平均值
缓存结果并且不重新计算它们。
Return从格子0转为获胜
是的，这似乎没什么不明显的。动态编程似乎不做任何不明显的事情，在朴素算法的中间有一个适当限制的缓存。
诀窍是将问题安排为具有良好边界的缓存，从而使天真的算法崩溃而无法做太多工作。
单人棋盘游戏。该板由一排 n 个单元格组成，从左到右编号为 1 到 n 正确的。单元格“j”包含一个正整数 cj。 规则是这样的：
- 您从最左边的单元格开始。
- 在每一轮中，您掷出一个公平的 6 面骰子，结果数字为 A。你 向前移动 A × cj 个单元格，其中 j 是您所在单元格的索引 上。
- 退出棋盘即为赢，即指数 j > n 为赢。
例如，考虑大小为 n=10 的棋盘 首先，您位于第一个值为 c1 = 2 的单元格中。在第一轮中，您掷骰子 并获得一个值 1，所以你向前移动 2 个单元格。然后在下一次掷骰中，您在单元格 3 上掷出 5 （c3 = 4），所以你向前移动 20 个单元格会让你退出棋盘。你赢了！！你拿了 2 轮到赢了。
如何使用运行时间为 (n) 的动态规划算法计算上述游戏获胜所需的预期回合数？
您要查找的递归关系是：
E[j] = 0 (if j > n)
E[j] = 1 + 1/6 * sum_k(E[j + k * c_j]) (otherwise, for k \in 1..6)
对于每个单元格，计算平均获胜的回合数。
对于 k>=n 的单元格[k]，这是 0。
对于其他k 缓存结果并且不重新计算它们。 Return从格子0转为获胜 是的，这似乎没什么不明显的。动态编程似乎不做任何不明显的事情，在朴素算法的中间有一个适当限制的缓存。 诀窍是将问题安排为具有良好边界的缓存，从而使天真的算法崩溃而无法做太多工作。