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

面试时的时候，面试官问了我一个算法题，题目大概是这样的：一个手机键盘上的数子0-9（也就是九宫格键盘），假如有两个机械臂a和b，初始位置都在0数字上，机械臂移动一步都会消耗一定的能量，问随意给定一个手机号码，两个机械臂怎样移动才会消耗最少的能量把手机号码打印出来。

希望大家给个思路，我觉得是动态规划吧，最后能把代码贴出来，谢谢了……

全部评论

推荐最新楼层

我来讲一个冷笑话

University of Helsinki C++

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

点赞回复分享

发布于 2016-09-03 09:30

牛客1481368号

东北大学 C++

#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; }

点赞回复分享

发布于 2016-09-03 09:19

Horanol

字节跳动_Data-商业化技术_后端开发

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

点赞回复分享

发布于 2016-09-02 23:22

牛客492426号

Java

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

点赞回复分享

发布于 2016-09-02 22:15

呵呵哒2333

北京理工大学 C++

这个手机号码是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)。

点赞回复分享

发布于 2016-09-02 22:10

cc98

浙江大学 C++

双层的DP

点赞回复分享

发布于 2016-09-02 21:32

金八铜九炮灰十

蓝翔职业技术学校

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

点赞回复分享

发布于 2016-09-02 21:30