第三十六天(极小化极大)

今天完成题目:866,486,375 866:石子游戏

• 转换思想,有一个总分,自己先手则最大化,敌人先手则最小化

• 最终判断总分是否大于0,若是,则说明自己先手胜利

• 此题答案恒为True,因为(先手可以选择所有的奇数堆或者偶数堆,对手只能选择和你相反的选择)

  • 显然，亚历克斯总是赢得 2 堆时的游戏。 通过一些努力，我们可以获知她总是赢得 4 堆时的游戏。

  • 如果亚历克斯最初获得第一堆，她总是可以拿第三堆。 如果她最初取到第四堆，她总是可以取第二堆。第一 + 第三，第二 + 第四 中的至少一组是更大的，所以她总能获胜。

  • 我们可以将这个想法扩展到 N 堆的情况下。设第一、第三、第五、第七桩是白色的，第二、第四、第六、第八桩是黑色的。 亚历克斯总是可以拿到所有白色桩或所有黑色桩，其中一种颜色具有的石头数量必定大于另一种颜色的。

# 高阶函数
from functools import lru_cache
class Solution:
    def stoneGame(self, piles):
        N = len(piles)
        # last recently unused,缓存,None表示无限制
        @lru_cache(None)
        def dp(i, j):
            # The value of the game [piles[i], piles[i+1], ..., piles[j]].
            if i > j: return 0
            parity = (j - i) % 2 # 判断是否是亚历克斯(先手)
            if parity == 1:  # first player
                return max(piles[i] + dp(i+1,j), piles[j] + dp(i,j-1)) # 越大,越能获胜
            else:
                return min(-piles[i] + dp(i+1,j), -piles[j] + dp(i,j-1)) # 越小,越能减少对手获得的分数

        return dp(0, N - 1) > 0

486:预测赢家

• 类似866,但是起始的数量不一定是偶数

• 可以使用866的方法,略加修改即可

375:猜数字大小 二

• 遍历所有的1-n中的i,可以获得所有的耗费,选择最小的耗费

• cost(1,n)=i+max(cost(1,i−1),cost(i+1,n))

• 方法有两种:

  • 方法一,利用lru_cache和函数递归

  • 方法二,利用dp数组(也是cost数组)

# 方法一
from functools import lru_cache
class Solution:
    def getMoneyAmount(self, n: int) -> int:
        # dp = [0,0,1,3,4,6,8,10]
        
        @lru_cache(None)
        def dp(i,j):
            '''
                dp(i,j):从i-j所需要的最少能保证赢的钱数
            '''
            if i>=j:
                return 0
            else:
                num = 0xffffffff
                for x in range(i,j+1): # 假设猜了x
                    temp = max(dp(i,x-1),dp(x+1,j))+x # 左右两边中更花钱的可能(为了保证赢)
                    if num>temp: # 选择更少的(为了用最少的花费保证能赢)
                        num = temp
                return num
        return dp(1,n)