面试时遇到的一个算法题，请教大家

各个数字之间的距离集合中求最小和，初步想法……

0-9一共10个数，哪来的九宫格？

双层的DP

这个手机号码是11位的，搜索空间很小，用普通的搜索就行了：(pos1, pos2, index) = Min(dis(pos1, telnum[index]) + (telnum[index], pos2, index+1) /*第一个机械臂从pos1移动到telnum[index]*/，dis(pos2, telnum[index]) + (pos1, telnum[index], index+1)) /*或者第二个机械臂从pos2移动到telnum[index]*/ ； (pos1, pos2, 11) = 0。 （其中dis函数是两个按键的移动消耗，O(1)的复杂度），然后可能会出现重复计算，那么就加个记忆set保存计算过的结果，还有（pos1, pos2, index） == (pos2, pos1, index)。

让a去找第一个数字，达到后，a在第一个数字位置，b在0，计算a和b距离第二个数字的距离，谁近谁走，依次类推 （感觉就是计算两个点到第三个点的距离，近的变成第三个点，距离相等走a，再继续计算，个人想法，仅供参考，不知道对不对...）

这不是一个局部最优的题，不能用贪心算法，也就是不能每一步都取距离最小的值，这样总的步数未必是最小的。

#include<iostream> #include <vector> using namespace std; int DistanceArry[10][10]; int Mindistance=INT_MAX; int arry[11]; int point[2]; void DFS(int index,int value) { if(index==11) { if (value<Mindistance) { Mindistance=value; return ; } } else { for(int i=0;i<2;i++) { int tmp=point[i]; int addvalue=DistanceArry[point[i]][arry[index]]; point[i]=arry[index]; DFS(index+1,value+addvalue); point[i]=tmp; } } } int main() { for(int i=0;i<11;i++) { cin>>arry[i]; } point[0]=point[1]=0; for(int i=0;i<10;i++) { for(int j=i;j<10;j++) { if(i==0) { DistanceArry[j][0]=DistanceArry[0][j]=(11-j)/3+(11-j)%3; } else { DistanceArry[i][j]=DistanceArry[j][i]=((j-i)/3)+(j-i)%3; } } } DistanceArry[0][0]=0; DFS(0,0); cout<<Mindistance<<endl; }

因为数字不多，可以动态规划吧。 数字个数1，返回a,b里移动距离最小的。 数字个数大于1，返回min（a移动距离+剩下n-1个数字移动距离最小的，b移动距离，+剩下n-1个数字移动距离最小的。