侯瑞哲的博客

Ruizhe's Blog

0%

解决博弈问题的动态规划通用思路

发表于 更新于 Valine： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# 解决博弈问题动态规划通用思路.py


# 我们把石头游戏改得更具有一般性
# 你和你的朋友面前有一排石头堆，用一个数组piles表示
# piles[i]表示第i堆石子有多少个。
# 你们轮流拿石头，一次拿一堆，但是只能拿走最左边或者最右边的石头堆。
# 所有石头被拿完后，谁拥有的石头多，谁获胜
# 假设两人都很聪明，请你设计一个算法，返回先手和后手最后得分（石头总数）之差
# 比如：
# piles = [1, 100, 3]
# 先手能得4分，后手能得100分，返回-96


# 思路
# 子问题
# 在第i到第j堆石头，先手能获得最大石头数是多少，后手是多少
# 定义状态数组
# f(i, j, 0) f(i, j, 1) 表示第i到第j个石头，包括第i和第j个，0表示先手，1表示后手
# 因为两人都极聪明，先手选完就变后手，来回交替的
# 递推方程
# f(i, j, 0) = max 拿左边 f(i+1, j, 1) + a[i]
#            =     拿右边 f(i, j-1, 1) + a[j]
# 知道了拿左边还是右边后
# f(i, j, 1) =     先手拿左边 f(i+1, j, 0)
#            =     先手拿右边 f(i, j-1, 0)
# 初始化
# f(i, i, 0) = a[i] 只有一堆石子的时候，先手为该堆石子个数，后手就为0
# f(i, i, 1) = 0
# 返回值
# f(0, n-1, 0) 先手最终石子数 - f(0, n-1, 1)后手最终石子数
# 优化空间复杂度
# 是对角线的递推，这种情况最好不要优化空间，还可以利用计算机的缓存
from typing import List


class Solution:
    def game(self, piles: List[int]) -> int:
        if not piles:
            return 0
        n = len(piles)
        dp = [[[0] * 2 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i][0] = piles[i]
        for gap in range(1, n):
            for i in range(n - gap):
                j = i + gap
                left = dp[i + 1][j][1] + piles[i]
                right = dp[i][j - 1][1] + piles[j]
                # 先手选左边
                if left > right:
                    dp[i][j][0] = left
                    dp[i][j][1] = dp[i + 1][j][0]
                # 先手选右边
                else:
                    dp[i][j][0] = right
                    dp[i][j][1] = dp[i][j - 1][0]
        return dp[0][n - 1][0] - dp[0][n - 1][1]


def main():
    sol = Solution()

    piles = [1, 100, 3]
    res = sol.game(piles)
    print(res)


if __name__ == '__main__':
    main()
代表题目：
leetcode 877
1
2
3
4
5
6
7
# 也可以使用第2种解法
# 数学规律
#
# 先拿者可以拿到序号为 1,3,5...n-1 的石子堆，
# 也可以拿到序号为 2,4,6...n 的石子堆。
# 因为总石子数为奇数，所以这两种方式中，其中一种拿到的石子数大于另一种。
# 所以不按照拿尽量多的石子数，按照这种纯奇数序号或者纯偶数序号的方式拿，先拿者总可以赢。

dp解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
lass Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        if not piles:
            return True
        n = len(piles)
        dp = [[[0] * 2 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i][0] = piles[i]
        for gap in range(1, n):
            for i in range(n - gap):
                j = i + gap
                left = dp[i + 1][j][1] + piles[i]
                right = dp[i][j - 1][1] + piles[j]
                # 先手选左边
                if left > right:
                    dp[i][j][0] = left
                    dp[i][j][1] = dp[i + 1][j][0]
                # 先手选右边
                else:
                    dp[i][j][0] = right
                    dp[i][j][1] = dp[i][j - 1][0]
        return bool(dp[0][n - 1][0] - dp[0][n - 1][1])