LC 871 贪心方法的证明

楼主感觉这题的DP解法还算容易理解，贪心解法其实如果想的话感觉应该是对的，但是有没有什么好的方法证明它的correctness? 我对贪心算法一直觉得不太有意义的原因就是感觉即使想到了，也不确定correctness，就算AC了，也没法解释正确性，不知道面试的时候，一般interviewer会对贪心解法刨根问底么

看了一圈LC和LC-CN，都没找到让人满意的证明

我目前的想法是证明说，按照贪心的方法，如果至少需要加油 j 次，才能到达station i+1（即下一个station），那么：

x[ i ] + gas in the car right after leaving station i == dp[ i ][ j ]

这里：
x[ i ]是station i 的location,
dp[ i ][ j ]是按照动规方法下，只考虑station 0, station 1, ..., station i, 并且加油 j 次能到达的最远距离

这样的话相当于联系了贪心算法和DP算法，因为实质上动规就是穷举，贪心算法相当于减少了穷举的次数 （I assume...）

我的想法是首先肯定有x[ i ] + gas in the car right after leaving station i <= dp[ i ][ j ]
不过证明optimal这一步没太想明白，感觉就是说如果定义y = x[ i ] + gas in the car right after leaving station i，可以用归纳法证明，就是说如果y[k-1]成立的话，因为从y[k-1]到y[k]，j从j_{k-1}次加油变成了j_{k}次加油，那么因为贪心算法每次都是加最多的油，所以i = k也成立？

提前感谢~~~

补充内容 (2022-10-16 05:55 +8:00):
话说好像有个bug... 就是"[ i ]"之后的文字都是斜体，而且会把"[ i ]"自动删除掉。。。我这里打不出来所以i的前后加了两个空格