丧失记忆-1

顶级折磨：

我愿称其为顶级折磨。2号的题，做到7号，五天，整整五天，你知道我这五天是怎么过来的吗？我每天都在开双刀接嗜魂封魔斩接转换接开双刀接平A接上挑接崩山击接...

我每天都在思考加油站对于人类文明存续的意义以及四次元油箱的构造和.....

第一天：看到最少两个字，意识到可能是动态规划，但是不知道怎么定义状态所以睡了。

第二天：想了下，可不可以每次都选最远的那个加油站，是不行的。那么到底该怎么选择......想不出来。于是想，既然不知道怎么选，那就全都要。索性把所有的可能性都枚举出来，反正加油站数量才500。顺着这个思路，考虑怎么动态规划......虽然确定是动态规划了，但是依旧不知道怎么定义状态于是睡了。但是躺在床上突然想出来了：

子问题是到达第n个加油站为止，所有的加油站的选择方案。

状态是到达第n个加油站时，“经过的加油站数量和剩余的油量”的所有可能性。

n的状态从n前面所有可以到达n的加油站转移。

最终，剩余油量足够到达终点，并且加油次数最少的选择方案就是答案。

第三天：顺着前一天的思路，开始了coding......

此时我还没有意识到问题的严重性，直到：

然后我就傻了，这个例子的加油站才十几个，没有理由内存溢出。然后就想到，是不是JVM没有回收内存，然后就看了半天的JVM内存回收的帖子，发现主动触发内存回收，或者别的什么做法也好，都无法避免超出限制。于是在IDE里调试了一下，发现list的长度是指数上涨的......最后已经涨到百万级别了。

哦，对哦，n每加一次，组合的数量都会涨!n次。应该是n的阶乘次吧，反正这个总的组合数是很大的，大到哪怕n只有20，最终的值都已经超过int最大值好多倍了，500的话就是天文数字。

所以，枚举所有的选择不可行，需要排除一些选择。但是要怎么排除，没有概念，于是睡了。

第四天：经过一顿意☆义☆不☆明 的优化，最终前进了两个测试用例。然后......就没有然后了。睡了。

第五天：祭出调试大法，突然发现dp数组里有很多经过的加油站次数相等的值，这些值每次又会转移到n+1。于是想到，到达第n个加油站时，如果经过了相同的加油站数量，剩下的油多的方案，是一定优于油少的方案的，于是把List改成了Hashmap，对于每种加油站次数，只记录油最多的方案。这里是不能直接选择最少的加油次数的，因为不一定能到终点。

而且关键的问题是，到达第n个加油站的最少次数，和最终的次数，并不是最优子结构。

形象一点就是，第三个加油站给了30点油，起始油量最多可以到第三个加油站，那么选择它，但是第二个加油站如果给了10000的油，这个选择就错了，所以还是需要枚举所有情况。

经过一顿修改：

还是超时了。无敌的Hashmap，O(1)的查询效率，还是超时了......

但是至少证明了，我的想法是对的，所以，继续优化。

我把寻找答案的过程放到了前面的循环里，发现如果已经找到某个可以到达终点的min了，那么再遇到比min大的情况时，可以直接无视。经过这样的优化：

完美地。超时了。然后我发现，如果某个加油站的某种情况，无法到达当前加油站，那这种情况肯定也无法到达后面的加油站，可以直接去掉减少循环次数......

然后就有了最终版本的代码：

忐忑地点了提交，然后：

看到通过两个字的时候感动到哭了。

经典超过了百分之5的用户，让我回想起十年前电脑开机360弹出的击败百分之1的用户......

总算是没看题解自己想出来了，而且是用正宗动态规划做的，这样多少算是对DP有了一些掌握了吧。但是看了官方题解以后，发现我还是脑回路清奇，或者说，官方的思路对于来说还是太难了。

官方的动态规划只关注加油的次数和得到的总油量，这一点我确实想不到。我还是被困在汽车行驶的那种形象里，只想得到从前往后走，没有抽象出问题的本质......上次也是这样。

不过第一次不看题解做出了动态规划的题目，还是困难题，还是很开心的。

最近我才意识到，算法并不是某种方法或者工具，而是一种思想，只有习惯了这种思想才算真正掌握这种算法。

比如分治，动态规划，其实都是一种思想而不是具体的方法，这种思想可以用来解决任何问题，并不是和做题一样记住某个模板——

思想是需要去理解而不是记住的。