在常数时间内求解正负5，7，12从数轴上A走到B的最优路径解

一个非常有意思的问题，昨天睡觉之后一直在床上思考。

从数轴A点到B点，可以一次跳正负5，正负7，和正负12，求出到达B的最少步数和跳法（AB距离为整数）。

可以采用三叉树的结构进行递归求解，该想法需要对树结构有一定的理解。就是在跳到B点之前，必定是跳5，7，或12三种情况，那么可以递归求出这三种情况的解，哪一种值最小，哪个就是最优的解。但是可以估计，在递归数中，树的深度应该为O(n)（应为必定跳的步数应该为AB的距离n除以某一个系数），那么该种解法的时间复杂度是O(2^n).

我最开始的想法是用贪心算法，这样以最快的速度走到离B点的正负12范围之内，再常数步内一定能够到达B点（例如相差1时，3 * 5 - 2 * 7 = 1），但是这样有很多情况求出的不是最优解，而是和最优解非常接近的一个解。例如，AB相差15，那么应该最优解是 3 * 5 = 15，即每次跳5，一共三次到达。而不是首先跳12，再2 * 5 - 7.

因此贪心求出的不是最优解。

最后，好好思考一下，这个问题，和过程没有关系，也就是说，如果跳了x次5的距离，y次7的距离，z次12的距离，那么那一步先跳，哪一步后跳都没有关系，同时，如果你有一步5是向前走的，那么就不可能出现用5后退的情况（如果你这次后退了，那你前面前进的那次就是多此一举了）。好了也就是说，我们有x + y + z = n (AB的距离)，我们只要求解出s = |x| + |y| + |z|的最小值就可以了。

方程组，线性规划？

那么我们限定x, y, z可以求解出整数解，再找最小值，这样至少可以在O(n^3)的复杂度内求出结果（xyz至少可以限定范围与n相关，我可以说n较大时（n >10），总的步数不会超过n），我上面已经说过，贪心算法就可以保证以n/12步跳到离B正负12的范围之内，再常数步内可以跳到B点。

其实还可以接着思考另外一些问题，想好了，O(1)的复杂度的解法就出来了。

1. 不可能出现 x >0 && y >0的情况，因为这样就可以用一个12 （z 多取1）来替换一个 5 + 7；

2. 不可能出现 |x| > 6的情况，因为，例如x = 8，也就是说用5跳了8次，那么我可以用7跳5次，代替5跳的前面七次，即 40 = 5 * 8 = 5 * 7 +5 * 1 （8步) = 7 * 5 + 5 * 1（6步)

3. 同样，也不可能出现 |y| > 11的情况。

这样就将x,y限定在常数个取值范围之内了。

4. z > 0 （z只朝着B方向走），这个可以根据xy的范围列方程组进行证明；（这个可以不需要）

O(1)的解法：

方程组： 5x + 7y + 12z = n;

遍历x， y的取值，保证z 取整数，求解每次min = |x|+|y|+|z|的值，若小于原来的min则代替原来的取值，记录x，y，z的取值。

设 x, y, z, 分别为跳5，7，12的次数，n为AB的距离，min为跳的最少步数，a，b，c记录最优结果。

代码如下（欢迎指正）：

int findpath(int n){        int x, y, z, i, j;        int min = MAX, a, b, c, temp;        for (x = -6; x <= 6; x++)        {                for (y = -7; y <= 7; y++)                {                        if ((n - 5 * x - 7 * y) % 12 == 0 && x * y <= 0)                        {                                z = (n - 5 * x - 7 * y) / 12;                                temp = ab(x) + ab(y) + ab(z);                                if (temp < min)                                {                                        min = temp;                                        a = x;                                        b = y;                                        c = z;                                }                        }                }        }        printf("a = %d, b = %d, c = %d, min = %d\n", a, b, c, min);        return 0;}