下面是这个问题的描述：
给你两个整数a和b，你想找到把a转换成b所需的最短操作序列，在这里你可以在每一步上加或减5、7或12。
例如，如果给定a=-5和b=19，则最短路径为
-5 + 12 + 12 = 19
如果给你1和3，最短的路径是
1 + 7 - 5 = 2
我唯一能想到解决这个问题的方法就是使用bfs，也许再做些修剪。有没有更好的算法可以代替？
谢谢！
最佳答案
让我们从一组有趣的观察开始。正如许多其他人所指出的，目标是找到一些具有整数系数的线性组合5x+7y+12z=b-a，使得x+y+z最小化。但我们可以利用这三个数字之间的一些非常有趣的联系：
如果我们有一个5x+7y+12z的组合，其中x和y都是正的或都是负的，我们可以取消一些x和y，以增加一个相等的12s。换句话说，没有一个最优解在x和y上都有相同的符号，因为我们总是可以使这个解更好。
如果我们有一个5x+7y+12z的组合，其中y和z有相反的符号，我们总是可以去掉7和12，再加上5个适当的符号来得到更好的解决方案。同样地，如果x和z有相反的符号，我们总是可以去掉5和12，并添加7作为适当的符号。这意味着我们不需要考虑z与x或y符号相同的任何解，因为这意味着必须有更好的解。
让我们想想（1）和（2）共同告诉我们什么。（1）说x和y上的符号不可能相同，因为我们总是可以做得更好。（2）如果X和Z有相反的符号，或者Y和Z有相反的符号，我们总是可以做得更好。这意味着
引理：在最优解中，x、y或z中至少有一个必须为零。
要知道，如果这三个都是非零的，如果x和y有相同的符号，那么我们可以用12s来代替它们，很明显地使解更好，否则，x和y有相反的符号。因此，如果x和z有不同的符号，到（2）我们可以用更少的7来代替它们，否则y和z有不同的符号，到（2）我们可以用更少的5来代替它们。
好吧，这看起来真的很棒！这意味着我们只需要解这三个整数方程，然后找出系数和最小的一个：
5x+7y=b-a
5x+12z=B-A
7Y+12Z=B-A
幸运的是，通过Bezout's identity，因为gcd（5，7）=gcd（5，12）=gcd（7，12）=1，所有这些方程组都有b-a值的解。
现在，让我们看看如何求解这些方程。幸运的是，我们可以使用一些可爱的技巧来大大减少我们的搜索空间。例如，对于5x+7y=b-a，x的值不能在[-6，+6]之外，因为如果是的话，我们可以将5的7替换为5的7。这意味着我们可以通过执行以下操作来求解上述方程：
对于x=-6到+6，看5x+7y=b-a是否有一个整数解，计算（b-a）-5x，看它是否可以被7整除。如果是，那么解决问题所需的步骤数由x+（（b-a）-5x）/7给出。
我们可以使用类似的技巧来求解后两个方程-对于第二个方程，x的范围是-11到+11，对于第三个y的范围也是-11到+11。然后我们可以从这三个方程中选出最好的答案，看看答案是什么。
这里有一些伪代码来记录尽可能少的步骤。只需记录使用了哪种解决方案，然后将其扩展到完整路径中，就可以轻松地修改此选项以返回这些步骤：
Let best = infinity
# Solve 5x + 7y = b - a
for x = -6 to +6:
if ((b - a) - 5 * x) mod 7 = 0:
best = min(best, |x| + |((b - a) - 5 * x) / 7|)
# Solve 5x + 12y = b - a
for x = -11 to +11:
if ((b - a) - 5 * x) mod 12 = 0:
best = min(best, |x| + |((b - a) - 5 * x) / 12|)
# Solve 7x + 12y = b - a
for x = -11 to +11:
if ((b - a) - 7 * x) mod 12 = 0:
best = min(best, |x| + |((b - a) - 7 * x) / 12|)
return best;
这个算法惊人的快速-它在O（1）时间内运行，因为求解每三个线性系统所需的迭代次数是一个常数（最多23次）。它只需要O（1）内存来保存可能的值，我认为在实践中它可能是您能够编写的最快的算法。
希望这有帮助！