d*w
1 楼
某个公司的面试题，算是我见过最难的了。
给出一个棋盘，比如10*10大小，有2个选手，每个人交替下。每个人手上有7个字母可
以用，给定一个字典
第一问 只考虑一个棋手，
他需要利用手中的字母，放在棋盘上空格中，必须是一个单词（单词可以在字典中查到
），每个字母会有个权重，目标是value最大化。
例如：7个字母为：
a, a, a, b, d, n, n
如果字典里面存在如下单词
and
band
banana
而权重表
a:1
b:2
d:3
n:5
那么他的策略是选个最大的，banana value:15
第二问：考虑到第二个棋手
他也是要利用手上的7个字母，放若干在棋盘上，他必须放在棋手1相邻的位置上，比如
他的上一行，或者右边紧邻的一列，只能横放或者竖放，但必须是跟之前的单词有交接
的，而且他要保证棋盘上有字母的每一行，每一列都是个单词,
如：
他手上的字母是：h,u,n,t,i,n,g
h
u
b a n a n a
t
i
n
g
最后目标是棋盘上的单词价值最大化。
给出一个棋盘，比如10*10大小，有2个选手，每个人交替下。每个人手上有7个字母可
以用，给定一个字典
第一问 只考虑一个棋手，
他需要利用手中的字母，放在棋盘上空格中，必须是一个单词（单词可以在字典中查到
），每个字母会有个权重，目标是value最大化。
例如：7个字母为：
a, a, a, b, d, n, n
如果字典里面存在如下单词
and
band
banana
而权重表
a:1
b:2
d:3
n:5
那么他的策略是选个最大的，banana value:15
第二问：考虑到第二个棋手
他也是要利用手上的7个字母，放若干在棋盘上，他必须放在棋手1相邻的位置上，比如
他的上一行，或者右边紧邻的一列，只能横放或者竖放，但必须是跟之前的单词有交接
的，而且他要保证棋盘上有字母的每一行，每一列都是个单词,
如：
他手上的字母是：h,u,n,t,i,n,g
h
u
b a n a n a
t
i
n
g
最后目标是棋盘上的单词价值最大化。
