LeetCode 818赛车问题动态规划解法的正确性证明问询

问题重述 #

赛车从数轴位置0出发，初始速度为+1，支持两种指令：

• A：位置 += 当前速度，速度 *= 2
• R：速度取反（正变-1，负变1），位置不变
  给定正整数目标位置target，求到达该位置的最短指令序列长度。

DP解法回顾 #

定义DP[i]为到达右侧位置i所需的最短指令数，初始条件DP[0] = 0，更新规则分为三种情况：

1. 短射后往返复用：先无倒车到达j < i（用n次A，j=2^n-1），倒车（1次R）后前进k次A到达位置j - (2^k-1)，再倒车（1次R）复用DP[i - (j - (2^k-1))]，总指令数为n + 2 + k + DP[i - (j - (2^k-1))]
2. 超射后倒车复用：先无倒车到达j > i（用n次A，j=2^n-1），倒车（1次R）后复用DP[j - i]，总指令数为n + 1 + DP[j - i]
3. 直接到达：若i=2^n-1，则DP[i]=n（直接n次A）

核心正确性证明 #

疑问1：为何最优路径不会先倒车到a < 0，再前进到j > i，最后倒车复用DP[j - i]？ #

假设存在这样的路径：0 →(R + A*p)→ a < 0 →(R + A*q)→ j > i →(R + A*r)→ i，总指令数为1+p+1+q+1+r = p+q+r+3。

构造更优替代路径：直接从0用q'次A到达j' >= j（q'是满足2^{q'}-1 >=j的最小整数），再倒车复用DP[j' -i]，总指令数为q' +1 + DP[j' -i]。

对比两者：

• 原路径从0到a再到j的过程，需要先倒车到负位置，再前进抵消负距离并到达j，指令数p+q+2必然大于等于q'（直接前进到j的最少指令数）。
• 原路径中从j到i的指令数r等于DP[j-i]，而DP[j'-i]是到达j'-i的最短指令数，因此r >= DP[j'-i]。

综上，原路径总指令数p+q+r+3 >= q' +1 + DP[j'-i]，替代路径更短，因此该假设路径不可能是最优。

疑问2：为何不会超射到j > 2i后倒车返回i？ #

首先证明这种路径不存在可行解：
若存在超射j=2^n-1 >2i，倒车后用m次A到达i，则位置满足：
j - (2^m -1) = i（倒车后速度为-1，m次A的位移是-(2^m-1)）
代入j=2^n-1得：
2^n -1 - (2^m -1) = i → 2^n - 2^m = i

由于j>2i，代入得：
2^n -1 > 2*(2^n -2^m) → 2^n -1 > 2^{n+1} - 2^{m+1} → 2^{m+1} > 2^n +1
两边除以2得：2^m > 2^{n-1} + 0.5，即m >=n。

但i=2^n-2^m >0要求2^n>2^m，即n>m，与m>=n矛盾。因此，不存在这样的整数m使得超射到j>2i后能通过倒车加A指令到达i，这种路径本身不可行，自然无需考虑。

结论 #

所有可能的最优路径都被DP解法的三种情况覆盖，因此该DP解法是正确的。

内容的提问来源于stack exchange，提问作者punypaw