利扣656的coin path为什么只能使用dp walk backward解决？

如果使用dp的walk forward方法，得不出lexiographucally ordered path 即下面这个方法是错的：

[size=14.6667px]如果我们在dp forward的时候已经定义dp[size=14.6667px]为从i左边B个位置里的最小cost， 并同时记录path[size=14.6667px]从i左边B个位置里的最小cost的位置来源，以此写出dp forward的思路：首先初始化

1. dp[0] = A[0]
   
2. for i in [1, A.size()]{
   
3.         for j in [max(0, i-B), i]{ //j是i往**左**至多B位
   
4.         if (dp[i] == dp[j] + A[i] && pos[i] > j) {
   
5.             pos[i] = j;
   
6.         }
   
7.         if (dp[i] > dp[j] + A[i]) {
   
8.             dp[i] = A[i] + dp[j];
   
9.             pos[i] = j;
   
10.         }
    
11.         }
    
12. }[/i][/i][/i][/i][/i][/i][/i][/i][/i]

复制代码

正确的是利用 dp backward:

1. <i>dp[n-1] = A[n-1]</i>
   
2. <i>for i in [A.size()-2, 0]{</i>
   
3. <i>        for j in [i+1, min(i+B, n)]{ //j是i往**右**至多B位</i>
   
4. <i>        // 连dp</i><i style="font-style: italic;"> == dp[j] + A<i>的情况都不需要讨论
   
5.         if (dp<i> > dp[j] + A<i>) {
   
6.             dp<i> = A<i> + dp[j];
   
7.             pos<i> = j;
   
8.         }
   
9.         }
   
10. }
    
11. </i></i></i></i></i></i></i>

复制代码

仔细看了一下这个discussion https://discuss.leetcode.com/top ... nb-time-o-n-space/8  里面只提到dp forward会丢失optimal prefix path for each subproblem， 所以用dp forward 必须记录能抵达当前A的optimal path。

比如test case [0,0,0,0,0] B=3, 如果利用dp forward的逻辑 那么在index=2的位置我们会往左考虑index=0,1两个位置 ：
如果首先考虑index=1 则path[2]会更新为1,dp[2]=0. 那么当我们考虑更左边的index=0时 首先dp[2]不会因为index=0时的更小，而path[2]=1 >0 因此path[2]就更新为0. 这个地方就错了
如果首先考虑index=0 则path[2]会更新为0,dp[2]=0. 那么当我们考虑更右边的index=1时 首先dp[2]不会因为index=1时的更小，而path[2]=0 < 1 因此path[2]根本不更新. 这个地方也错了.
[size=14.6667px]这个结论很明显，但是没有理解为什么会lost optimal prefix path,也没说为什么用dp backward能保证不lost optimal prefix path。既然在一开始[size=14.6667px]在dp forward的时候已经定义dp为从i左边B个位置里的最小cost， 并同时记录path[size=14.6667px]从i左边B个位置里的最小cost的位置来源， 为什么会[size=14.6667px]丢失optimal prefix path for each subproblem， 而dp backward的解法不[size=14.6667px]会[size=14.6667px]丢失呢[size=14.6667px]（虽然利扣discussion利用数学归纳法能证明）？