如何改進這個動態編程解決方案？

Question

原始問題描述Pile it up

摘要：雙方A和B玩的遊戲包含2堆X和Y硬幣。每轉一圈，他可以執行以下操作中的一個：

• 從單個樁移除任何數量的硬幣（至少1個硬幣）
• 來自兩個堆
• 取出硬幣的相同量的傳遞轉。這仍然算作一回合。

遊戲結束時，不可能移動，不能移動的玩家輸了。兩位球員都打出最佳狀態。雙方玩家在比賽開始前計算比賽結果。失敗的玩家試圖最大限度地提高遊戲中的回合次數，並且贏得勝利的玩家會盡量減少回合。沒有玩家可以超過P次。 A開始遊戲。輸出由一個空格分隔的贏家名稱和遊戲中的移動次數。 0 < = X，Y，P < = 1000

我想出了一個O（n^3）DP解決方案，但對於考慮邊界的這個問題肯定不夠好。如果這是你的轉牌，那麼讓d [i，j]爲最小轉牌圈數，並且分別在堆X和Y中留下i和j硬幣。然後我們有：

d[i, j] = 0 if i = j = 0 
      1 if (i = 0 && j > 0) or (i > 0 && j = 0) or (i = j && i > 0) 
      min(min(d[i-p, j]), min(d[i, j-q), min(i-r, j-r)) if a each substate is a losing position 
      max of all winning position substate if no losing substate is found 

最後，d[i,j] = d[i,j] + 2*P if [i,j]是獲勝狀態，你會不會從一開始就立即獲勝。從上面的公式可以看出，這是一個O（n^3）的解決方案。我想改進O（n^2）的解決方案，我該如何重新表達問題？

Answer 1

首奪位置

1. 1空樁
2. 兩樁與相同數量的硬幣

的時候會傳球的球員輪到他？
假設職位是（3,2），那麼他有3個選項。

1. 他可以移動到（2,2），但是這使得它成爲了對手的獲勝位置。
2. 他可以移動到（1,0），但這又是對手的獲勝位置。
3. 如果他選擇跳過轉彎，那麼對手也可以跳過轉彎。這個跳躍最多可以進行P轉。

根據P的奇偶性（P是偶數還是奇數）以及根據誰開始跳過序列，我們可以找出贏得的人。找到轉數並不困難。

爲什麼跳過序列是最優的？
那麼如果你輸了，你會希望再呆在比賽中（如遊戲規則中所給出的那樣）。即使我知道基於P的平價我會輸，我可以推遲它通過P轉。有意義嗎？
我鼓勵您使用這種洞察力來加快算法的速度，但如果您在實現時遇到問題，請提出問題！