博弈_动态规划，递归与模拟

一：动态规划

题目链接：486. 预测赢家 - 力扣（LeetCode）

总体思路是使用动态规划（DP）的方法来解决一个两人轮流从数组的两端取数，并计算最终得分差的问题。动态规划是一种将复杂问题分解成更小的子问题来解决的优化技术。

def can_win(nums):# 定义一个辅助函数，用于递归计算在数组索引i到j范围内，玩家1相对于玩家2的最大得分差def helper(i, j, memo):# 如果i大于j，说明当前范围内没有数字可以取，返回得分差为0if i > j:return 0# 如果memo字典中已经存储了索引i到j范围内的得分差，直接返回这个值，避免重复计算if (i, j) in memo:return memo[(i, j)]# 玩家1选择最左边的数字，计算在这种情况下玩家1相对于玩家2的得分差# 玩家1得分增加nums[i]，玩家2在剩余数组[i+1, j]中选择最优策略left = nums[i] - helper(i + 1, j, memo)# 玩家1选择最右边的数字，计算在这种情况下玩家1相对于玩家2的得分差# 玩家1得分增加nums[j]，玩家2在剩余数组[i, j-1]中选择最优策略right = nums[j] - helper(i, j - 1, memo)# 玩家1会选择使得自己得分差最大的策略，存储在memo字典中memo[(i, j)] = max(left, right)# 返回当前索引范围内玩家1的最大得分差return memo[(i, j)]# 初始化一个字典用于存储子问题的解，避免重复计算memo = {}# 从整个数组开始计算，即从索引0到len(nums)-1# 如果最终计算得到的得分差大于等于0，则玩家1可以赢，返回True；否则返回Falsereturn helper(0, len(nums) - 1, memo) >= 0

辅助函数 helper：这个递归函数用于计算在数组索引i到j范围内，玩家1相对于玩家2的最大得分差。它考虑了玩家1从两端取数的所有可能情况，并存储了子问题的解以避免重复计算。
动态规划状态 memo：使用一个字典来存储子问题的解，这是动态规划中的“备忘录”技术，用于优化递归过程。
递归终止条件：当i大于j时，表示当前范围内没有数字可以取，得分差为0。
返回值：函数最终返回一个布尔值，表示玩家1是否能够赢得游戏。如果玩家1的得分差大于等于0，则认为玩家1可以赢。

二：递归

题目链接：3227. 字符串元音游戏 - 力扣（LeetCode）

总体思路如下：

首先定义count_vowels函数用于计算一个字符串中的元音字母数量。
helper函数是核心的递归函数，用于判断小红是否能赢得游戏。它通过两层循环遍历输入字符串s的所有子串，当找到一个子串的元音个数为奇数（符合小红的操作规则）时，就假设小红移除这个子串，然后递归调用helper函数判断小明面对新字符串的结果，由于是判断小红能否获胜，所以取反小明的结果（小明输则小红赢），并将所有可能情况进行逻辑或运算（只要有一种情况小红能赢则最终结果为小红能赢）。
winnerOfGame函数作为对外接口，直接调用helper函数并返回结果。

# 计算字符串中元音字母的数量
def count_vowels(s):vowels = "aeiou"count = 0# 遍历字符串中的每个字符for c in s:# 如果字符是元音字母，增加计数if c in vowels:count += 1return count# 辅助函数，用于递归地判断小红是否能赢
def helper(s):# 如果字符串为空，说明当前玩家（此时是小明）无法操作，小红输if not s:return False# 小红先手，初始设为不能赢win = False# 遍历字符串的所有子串for i in range(len(s)):for j in range(i + 1, len(s) + 1):sub = s[i:j]sub_count = count_vowels(sub)# 如果子串中的元音个数为奇数（小红可移除该子串）if sub_count % 2 == 1:# 移除该子串后，判断小明的结果，取反是因为如果小明不能赢则小红赢next_win = not helper(s[:i] + s[j:])win = win or next_winreturn win# 主函数，调用辅助函数判断小红是否能赢
def winnerOfGame(s):return helper(s)

这段代码通过递归的方式模拟了小红和小明玩字符串元音游戏的过程。通过穷举小红所有可能的操作（移除奇数个元音的子串），然后递归判断小明面对新字符串的结果来确定小红是否能赢得游戏。

三：模拟

示例1

题目链接：2038. 如果相邻两个颜色均相同则删除当前颜色 - 力扣（LeetCode）

总体思路如下：

定义内部函数can_delete：这个函数用于判断当前玩家是否能够删除指定颜色的片段。根据传入的玩家标识（'A'或'B'）确定目标颜色，然后遍历字符串中间部分（因为两端的片段不能删除），查找满足条件（自身颜色与左右相邻颜色相同）的颜色片段，如果找到就返回该片段的索引，否则返回 -1，表示不能删除。
主循环部分：使用while True创建一个无限循环来模拟游戏过程。在每次循环中，首先判断是否是Alice的回合，如果是，调用can_delete函数检查Alice是否能够删除'A'颜色片段，如果不能（返回 -1），则Alice输，返回False；如果可以，就更新字符串（移除该颜色片段）。如果不是Alice的回合（即Bob的回合），则进行类似的操作，不过是针对'B'颜色片段，如果Bob不能删除，Bob输，返回True（表示Alice赢）。每一轮结束后，通过alice_turn = not alice_turn切换回合。

def winnerOfGame(colors):# 定义内部函数，用于判断当前玩家是否可以删除某个颜色片段def can_delete(s, player):# 根据当前玩家确定要操作的目标颜色if player == 'A':target = 'A'else:target = 'B'n = len(s)# 遍历字符串中间部分（两端不能删除），查找满足条件的颜色片段for i in range(1, n - 1):if s[i] == target and s[i - 1] == target and s[i + 1] == target:# 如果找到，返回该片段的索引return i# 如果没有找到，返回 -1，表示无法删除return -1alice_turn = Truewhile True:# 如果是Alice的回合if alice_turn:# 检查Alice是否可以删除 'A' 颜色片段index = can_delete(colors, 'A')if index == -1:# 如果不能删除，Alice输，返回Falsereturn False# 如果可以删除，更新字符串，移除该颜色片段colors = colors[:index] + colors[index + 1:]else:# 如果是Bob的回合，检查Bob是否可以删除 'B' 颜色片段index = can_delete(colors, 'B')if index == -1:# 如果不能删除，Bob输，返回True（Alice赢）return True# 如果可以删除，更新字符串，移除该颜色片段colors = colors[:index] + colors[index + 1:]# 切换回合，下一轮是另一个玩家的回合alice_turn = not alice_turn

这段代码通过定义内部函数判断可删除片段和主循环模拟游戏回合的方式，有效地解决了Alice和Bob在特定规则下玩颜色片段删除游戏谁会获胜的问题。通过循环和条件判断准确地模拟了游戏过程。

示例2

题目链接：1561. 你可以获得的最大硬币数目 - 力扣（LeetCode）

总体思路如下：
目的是计算在给定的硬币堆中，按照特定的取币规则，你可以获得的最大硬币数。首先，我们对硬币堆进行降序排序，确保最大的硬币堆在列表的前面。然后，我们通过遍历排序后的列表，但只取索引为奇数的元素（即第二大的硬币堆），并将其值累加到 total_coins 中，因为这些是你能取走的硬币堆。最后，返回累加的总硬币数，这就是你可以获得的最大硬币数。

def max_coins(piles):# 对硬币堆进行降序排序，使得我们可以方便地获取最大的硬币堆piles.sort(reverse=True)# 初始化变量，用于存储你可以获得的总硬币数total_coins = 0# 遍历排序后的硬币堆列表，从索引1开始，即第二大的硬币堆，每次跳过两个硬币堆# 这样做是因为在每一轮中，Alice 取走最大的，你取走第二大的，Bob 取走第三大的# 我们只需要计算你能取走的硬币数，即每次遍历的当前硬币堆for i in range(1, len(piles) // 3 * 2, 2):total_coins += piles[i]# 返回你可以获得的总硬币数return total_coins

在讨论的硬币分配游戏中，采取特定的策略（即从最大的三个硬币堆中选择第二大的那个）是基于以下几个原因：

游戏规则：根据游戏规则，Alice取走最大的那一堆，你取走第二大的那一堆，Bob取走最小的那一堆。因此，为了最大化你的收益，你应该总是从最大的三个硬币堆中选择第二大的那一堆。

排序优势：当你对硬币堆进行降序排序后，你可以确保在每一轮选择中，Alice取走的是当前最大的硬币堆，而你取走的总是仅次于Alice的那一堆。由于排序后最大的硬币堆总是被Alice取走，你取走的第二大的硬币堆在你的回合中是可获得的最大的。

最大化个人收益：通过选择第二大的硬币堆，你确保了自己在每个回合都能获得尽可能多的硬币。如果选择其他策略，比如随机选择或者选择不是第二大的硬币堆，你的总收益可能会减少。

对手行为：由于Alice总是取走最大的硬币堆，Bob取走最小的，你的选择实际上不受他们行为的影响。你的目标是最小化Alice和Bob的收益差距，而最大化自己的收益。

数学期望：在每一轮中，如果你总是选择第二大的硬币堆，从长远来看，你的总收益会是最高的。这是因为按照这种策略，你总是能够从最大的三个硬币堆中获取相对较高的收益。