Suppose you play the following game with your opponent:
There is a sequence of n coins with values v[1], v[2], …, v[n] in a queue which are known in advance. Now each player takes alternate turn to pick a coin. The rule is you can only take the coin from the head or from the tail of the queue each time.
Please design a dynamic program algorithm such that the total value of the coins you pick is the largest. We assume the opponent is very stupid and always makes an incorrect decision. We assume you make the first pick. Pseudo code is not required but you need
to show the inductive formula and initial conditions for the program. What is the complexity of your algorithm?
Apply your algorithm to the following sequence: 7, 5, 2, 3, 1, 6.
设L(i,j)是玩家i,i+1,i+2....j-1,j的所能获取的最大值。
假设从(i,j)序列开始取数，玩家可能获取的最大值应该是v(i)+L(i+1 , j ) 和 v(j) + L(i , j -1)中的最大值。对于L(i+1,j)队列而言，是对手先获取硬币，而且对手只能拿较小的硬币。所以对于具体的序列当v(i+1) > v(j) 时 L(i+1, j ) = ( i+1 , j-1) 。而当v(i+1) < v(j)时，L( i +1 , j ) = l( i＋2 , j )。所以最后可以推导出计算公式：
下面是 7 ， 5 ，2 ， 3 ， 1 ，6 序列的推导过程：
7(1,1) 7(1,2) 9(1,3) 12(1,4) 15(1,5) 18(1,6)
5(2,2) 5(2,3) 8(2,4) 8(2,5) 14(2,6)
2(3,3) 3(3,4) 3(3,5) 9(3,6)
3(4,4) 3(4,5) 9(4,6)
1(5,5) 6(5,6)
6(6,6)
__author__ = 'lun.wei'
class CoinGame :
def __init__(self , coins ):
self.coins = coins
self.coinNum = len(coins)
self.mTable = list()
self.mIndexTable = list()
for i in range( 0 , self.coinNum ):
tempList = list()
tempIndexList = list()
for j in range( 0 , self.coinNum) :
tempList.append( 0 )
tempIndexList.append( 0 )
self.mTable.append(tempList)
self.mIndexTable.append(tempIndexList)
def calu(self):
for j in range( 0 , self.coinNum):
i = j
while i >= 0 :
if i == j :
self.mTable[i][j] = self.coins[i]
self.mIndexTable[i][j] = ( j - i )
elif (j - 1) == i :
temp = self.coins[i]
self.mIndexTable[i][j] = 0
if self.coins[j] > self.coins[i] :
temp = self.coins[j]
self.mIndexTable[i][j] = j - i
self.mTable[i][j] = temp
else :
num1 = 0
num2 = 0
if self.coins[i + 1 ] > self.coins[j] :
num1 = self.coins[i] + self.mTable[i + 1 ][j - 1 ]
else :
num1 = self.coins[i] + self.mTable[ i+ 2 ][j]
if self.coins[i] > self.coins[j- 1] :
num2 = self.coins[j] + self.mTable[i][j-2]
else :
num2 = self.coins[j] + self.mTable[i+1][j-1]
self.mTable[i][j] = num1
self.mIndexTable[i][j] = 0
if num2 > num1 :
self.mTable[i][j] = num2
self.mIndexTable[i][j] = ( j - i )
i=i-1
def printChoose(self , end , begin , index ):
if ( end - begin ) < 2 :
if self.coins[end] > self.coins[begin ]:
print "%d: %d " %( index ,self.coins[end] )
else :
print "%d: %d " %( index ,self.coins[begin ] )
else :
if self.mIndexTable[begin][end] == 0 :
print "%d: %d " %( index , self.coins[self.mIndexTable[begin][end] + begin ] )
if self.coins[begin+ 1 ] > self.coins[end ] :
self.printChoose( end - 1 , begin + 1 , index + 1 )
else :
self.printChoose( end , begin + 2 , index + 1)
else :
print "%d: %d " %( index , self.coins[self.mIndexTable[begin][end] + begin ] )
if self.coins[begin] > self.coins[end - 1 ] :
self.printChoose( end - 2 , begin , index + 1 )
else :
self.printChoose(end -1 , begin + 1 ,index + 1 )
def outputAnswer(self):
print "Our Choice"
self.printChoose( self.coinNum - 1 , 0 , 1 )
def printMatrix(self , m ):
for i in range ( 0 , self.coinNum):
for j in range( 0 , self.coinNum ):
print "%8d" % (m[i][j]),
print
def printTable(self):
print "====Coins======"
print self.coins
print "=====MTABLE====="
#for i in range( 0 , self.coinNum ):
# print self.mTable[i]
self.printMatrix(self.mTable)
print "=====MINDEXTABLE====="
#for i in range( 0 , self.coinNum ):
# print self.mIndexTable[i]
self.printMatrix(self.mIndexTable)
game = CoinGame( [ 7 , 5 , 2 ,100 , 3 , 1 , 6 ])
game.calu()
game.printTable()
game.outputAnswer()
运行结果如下图：
