问题如下：
问题：
“您的汽车在无限数轴上从位置 0 开始，速度为 +1。您的汽车可以进入负位置。您的汽车根据一系列指令“A”（加速）和“R”（倒车）自动行驶：
当您收到指令“A”时，您的汽车会执行以下操作：
位置+=速度
速度 *= 2
当您收到指令“R”时，您的汽车会执行以下操作：
如果你的速度为正则速度= -1
否则速度=1
您的立场保持不变。
例如，在命令“AAR”之后，您的汽车将转到位置 0 --> 1 --> 3 --> 3，并且您的速度将变为 1 --> 2 --> 4 --> -1。
给定目标位置目标，返回到达该位置的最短指令序列的长度。”
来源：https://leetcode.com/problems/race-car/description/
建议的DP解决方案：
令 DP[i] 为向右移动距离“i”所需的指令数。
则 DP[0] = 0
对于我们的更新规则，有3种情况。
首先达到一些j < i without reversing, then reverse and travel some distance to k < j. Finally, reverse again and use the previously solved DP[i-k]
首先，在不逆向的情况下达到某个 j > i，然后逆向并使用之前求解的 DP[j-i]
我们不用倒车就可以到达i
根据上面的更新规则，我们可以从DP[0]到DP[i]求解，得到我们的解。
问题：
这似乎是这个问题被广泛接受的 DP 解决方案，但我还没有找到令人满意的证明，甚至根本没有任何证据来证明这个算法是正确的。
例如，如何证明遍历距离“i”的最佳方式不是立即反转并转到某个 a < 0, then reverse and travel to some j > i，最后再次反转并使用 DP[j-i]？
或者如何证明遍历距离“i”的最佳方法不是超出距离 j > 2i，然后反转并行进距离 2i - j > i，这是一个尚未解决的子问题已经解决了吗
我遇到的许多“证明”都做出了模糊的陈述，例如“应该明确的是，你不想超出 j > 2i”等等，这并不严格。
我现在的想法：
目前，我至少可以提出我认为有效的证明来证明我们永远不会想先反转到某个 a < 0, then reverse to some j > i，然后再回到 DP[j-i]。
我对此的证明是，在这种情况下，我们总共会反转 3 次。我们可以不这样做，而是简单地前往 j + a 而不反转，然后反转一次并转到 j，然后反转两次（反转一次将速度设置为 0，然后再次反转以指向 i）然后去i。我相信这最终会导致相同数量的步骤。
但是，我仍然无法证明为什么我们永远不会超调到某个 j > 2i 然后回到 i？
如果有人可以提供此解决方案的证明，我们将不胜感激，谢谢！
请注意，任何路径都可以分为零个或多个
AR如果 A 序列为空（长度为 0），则它不会移动汽车。否则，长度为 n 的 A 序列会将汽车沿其方向移动 2n-1 个位置。
请注意，您可以重新排列所有前向 A 序列和/或所有后向 A 序列，而不改变路径长度或行进距离，因此通常如果有一条最佳路径，则有很多条最佳路径。 您的更新规则只需覆盖这些最佳路径中的 1 条。
如果最优路径只有一个非空A序列，则适用更新规则3。
如果一条最优路径只有一个正向和一个反向非空 A 序列，则它仅由这些序列组成，并且适用规则 2。
如果最优路径有任何前向A序列等于或大于任何后向A序列，那么我们可以将这两个移动到路径的开头，并且规则1适用。
在其余情况下，所有后向 A 序列都比所有前向 A 序列长。这实际上是不可能的，因为总的前进距离必须更大。将每个前向 A 序列（除了“最小的”之外）与较大的后向 A 序列配对。如果最小的长度为 n，并且行进 2n-1，那么第二小的长度必须至少为 n，并且其配对反向序列行进的extra距离至少为 2n+1- 1 - 2n+1 = 2n。这比不成对的前向序列的行程更多，因此总路径行程无法前向。