我有时候会怀疑，解决复杂问题，是一种瘾。

这种复杂问题，包括一个解一个迷宫，拼一个乐高，做一道难题，通关一个超难的游戏。很多人一旦投入其中，就废寝忘食直到把它解决。甚至在解决之后，还继续不停寻找，然后接着沉迷其中。还比如，有类人被称为”工作狂“。他们加起班来没日没夜，多半也是陶醉在自己解决问题的”爱好“中。

从进化论的角度，也容易接受。那些生理上对解决问题有偏好的人，更容易被选择出来继续帮助自己的族群。同样的两个村庄，遇到干旱，有办法引水灌溉的，大概率会存活下来。从生理层面，也站得住脚。问题被解决，本身也有奖励性质。一旦自激，形成正循环，这种”成瘾“也就水到渠成。

既然是瘾，不妨再说一道Foobar的题，巩固一下我们的神经反射。

题目依旧是又臭又长。大意就是有一个量子油箱（一个数字），你可以选择三种操作，加一、减一或者减半（偶数时可）。问最少多少步，可以把这个数字变成1。

刚看完题，我心想，这是一道送分题啊。每次的操作固定，动态规划（DP）公式就基本确定了：

这里有个小优化，就是在选择操作时，优先选择”减半“。这个小”贪心“没有数学证明，不过如果想象一个二进制数100100，最快让他变小的操作，显然是右移，也就是”减半“。

通过了测试数据，又编了几个”大“数，也没什么毛病。提交……不出意外的又挂了。终于明白，简单的题目不可能是常态，踩坑才是。

回到题目，重新审题。在最后一段，找到了数据大小：

显然，300位长的数字，没法用默认类型来运算了。只能用近十年没用过的”数组“运算了。顾名思义，对于这种大数，可以把每一位分开，用一个数组存起来。四则运算时，模拟竖式，对每一位对应进行运算。

2. 如果末位是0，则直接做除二操作，当前步数+1

3. 如果末位是1，则分别递归求解+1和-1操作，步数取其中较小的+1

4. 边界值是数字1

显然直接递归多半会挂掉，所以这里我选择用队列(queue)存储中间状态，及其对应步数。遇到状态重复时，可以果断剪掉步数太多的状态。

复杂的问题，要先分解，再逐个击破。