這是 contest 的題目,在時限內沒有解出這一題,可惜。
雙方都會不會放水,採取最佳策略進行。這樣的情況下,如果是 Alice 贏就回傳 Alice,Bob 贏則 Bob,平手則 Tie。
這是一個博奕問題:有雙方,互相採取行動,兩者互相對抗。
當看到雙方都採取一樣的策略之時,雙方的判斷都是一樣的,因此用一個邏輯函數,就要能指出該下哪一步。
以拿走三顆石頭的時候來看,不論是此時是輪到 A 或者是 B ,兩者當前的最佳解都是一樣的。先後順序不影響決定最佳解,局面進行到哪裡才是。
因此,用一個 memo 記錄所有情形,其鍵會是拿走的數量或是剩餘的數量。這memo紀錄的分數對雙方都是一樣的。
接下來講一點博奕心理。
在選擇行動時,不一定會選擇當下分數最高的,如果最後要贏對手,採取行動原則是為了要讓自己領先對手加大差距,距離變化才是關鍵。
像是 -1 -2 -3 ,如果選擇分數最高的行動只拿 -1 ,對手會只拿 -2 ,最後你不得已只能拿 -3 而輸掉。
考量到對手的行動,你拿 -1 對手拿 -2 整體反倒被 對手拉近 1 的距離,若拿 -1 -2 對手會只能拿 -3,整體差距並沒有縮小,反到是更有利的選擇。
不過這沒提到後手再後手。你拿 -1 要思考對手的下一步, 而對手會思考對手的下一步再下一步,行動連鎖直到結束。連鎖到底,這種特性是遞迴。
整理一下觀察到的線索,推導出邏輯函數會是一個考慮拉大對手差距的遞迴函數。
那這個遞迴函數要回傳甚麼?
回到 -1 -2 -3 的例子,當你拿 -1,對手會採取最佳解,也就是剩下 -2 -3 的最佳拿法的分數。拿 -1 -2,也需要對手的最佳解。然後在三種選擇中,拿 -1 -2 是最佳解。
於是你可以找出當前狀況最佳解,回傳分數,遞迴往前傳,就能把最佳解一路往前推導。
最後來到起點,雙方一動也沒動的時候,此時由 Alice 先手,因此沒動過的最佳解,就是 Alice 的最佳下法的分數,如果為正的,意味著到最後 Alice 會贏那些分數。0則平手,負則輸掉。
class Solution: def stoneGameIII(self, stoneValue): stones = len(stoneValue) pos = 0 memo = {} # 使用座標當標籤 def searchMaxRelativeScore(pos): if pos in memo: return memo[pos] # 計算出當前剩餘個數 score = 0 scores = [] remains = min(stones - pos, 3) for i in range(remains): scores.append(sum(stoneValue[pos:pos+i+1]) - searchMaxRelativeScore(pos+i+1)) if scores: score = max(scores) memo[pos] = score return score searchMaxRelativeScore(0) if memo[0] > 0: return "Alice" elif memo[0] == 0: return "Tie" else: return "Bob"