经典动态规划：博弈问题 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：经典动态规划：博弈问题

评论礼仪 见这里，违者直接拉黑。

[fkjkkll]

n = piles.length
for 0 <= i < n:
for j <= i < n:
for who in {fir, sec}:
dp[i][j][who] = max(left, right)
第三行应该是"for i <=j<n:"吧

[zhoulinhui2018]

这也太难了吧

[deepbreath373]

力扣的石子游戏都到第九代了😂

[chansir1995]

哈哈,看到你的评论我还专门去看了,真的丧心病狂

[zzp-seeker]

提供一个简单版本：
主要递推式：f(l,r)=max(s[l]-f(l+1,r),s[r]-f(l,r-1)) 代表石头[l,r]区间内我的最大相对收益是多少
最后f(0,n-1)>0即为答案

class Solution:
    def stoneGame(self, s: List[int]) -> bool:
        n = len(s)
        vstd = [[-1]*(n+1) for _ in range(n+1)]
        def f(l,r):
            if vstd[l][r]!=-1: return vstd[l][r]
            if l==r: return s[l]
            vstd[l][r] = max(s[l]-f(l+1,r),s[r]-f(l,r-1)) # 相对收益
            return vstd[l][r]
        return f(0,n-1)>0

[labuladong]

@zzp-seeker 👍

[Heimda]

我想麻烦问一下东哥，dp数组在初始化为全pair(0, 0)的时候，我采取的是for-each的方式，但是明明这里是数组的引用，是有效的修改，但是为什么就是过不了？改成您的俩for初始化之后就能正常通过测试用例了...

错误实例：

     for(Pair[] temp : dp){
         Arrays.fill(temp, new Pair(0, 0));
     }

[labuladong]

@Heimda 盲猜，fill 并不会对 temp 的每个位置 new 一个 Pair，而是只 new 一个 Pair，然后 temp 里面全都是这个 Pair 的引用。

[Heimda]

@labuladong 谢谢 东哥赐教，自己这块学的不扎实，明白啦！感谢！

[NealCou]

这种DP数组的定义只能牢记了吧，写的跟艺术品似的🐮

[HelixGameEngine]

top-down 的解法更容易理解

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        cache = {}
        
        def fn(i, j):
            # if there's no stones, return
            if i > j:
                return 0
            
            if (i, j) in cache:
                return cache[(i, j)]
            
            # check if it's alice's turn.
            # since alice picks the stone first, 
            # alice always picks the stone at the even position of this subarray (not the original array)
            alice = True if (j - i) % 2 == 0 else False
            
            # if it's alice's turn, then alice could pick the first or last stone
            if alice:
                cache[(i, j)] = max(fn(i + 1, j) + piles[i], fn(i, j - 1) + piles[j])
            else:
                # if it's bob's turn, then bob could pick the first or last stone
                # decrease alice total score by bob's choice
                cache[(i, j)] = max(fn(i + 1, j) - piles[i], fn(i, j- 1) - piles[j])
            
            return cache[(i, j)]
        
        return True if fn(0, len(piles) - 1) > 0 else False

[gzmkobe]

对于877而言，答案是对的，但是过程个人觉得有点问题。 cache[(i, j)] = max(fn(i + 1, j) + piles[i], fn(i, j - 1) + piles[j])，这里如果用max的话就只能选当前first/last stone较大的那个值，当前小的值的路径永远不会被取到。

plus这个解法不适用于486。

[gzmkobe]

nvm。忽略我第一段。

[lupuswere]

这样也可以过，beat 100% :p

class Solution {
    public boolean stoneGame(int[] piles) {
        return true;
    }
}

[nuo1nuo]

东哥486题跟你所说的"更一般性的石头游戏"一样吧？不如把486题放入开头的”可解决的题目”里？

[labuladong]

@nuo1nuo 感谢提醒，已添加

[Yijia0106]

class Solution {
    int memo[][];
    public boolean PredictTheWinner(int[] nums) {
        memo = new int[nums.length][nums.length];
        for(int i=0;i<nums.length;i++) Arrays.fill(memo[i],-1);
        return dp(nums,0,nums.length-1)>=0?true:false;
    }

    public int dp(int[] piles, int i, int j){
        if(i>j) return 0;
        if(i==j) return piles[i];
        if(memo[i][j]!=-1) return memo[i][j];
        memo[i][j] = Math.max(piles[i]-dp(piles,i+1,j),piles[j]-dp(piles,i,j-1));
        System.out.println(memo[i][j]);
        return memo[i][j];
    }
}

请问这样的代码可以吗 大约速度超过30%左右 但是很好理解orz

[Yijia0106]

去掉System.out.println()之后速度80%了 orz

[labuladong]

@burushuijiaoba 打印输出是 IO 操作，很耗时的。

[Goolloo]

3D table

class Solution {
    public boolean stoneGame(int[] piles) {
        int size = piles.length;
        
        int[][][] dp = new int[size][size][2];
        
        for(int i = size-1; i >= 0; i--) {
            // when only 1 pile left, 1st hand get stones only
            dp[i][i][0] = piles[i];
            // more than 1
            for(int j = i+1; j < size; j++) {
                int left = piles[i] + dp[i+1][j][1];
                int right = piles[j] + dp[i][j-1][1];
                
                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][size-1][0] >= dp[0][size-1][1];
    }
}

Space Compression

diff[i][j] 
= dp[i][j][0] - dp[i][j][1]
= (piles[i] + dp[i+1][j][1]) - dp[i+1][j][0] or (piles[j] + dp[i][j-1][1]) - dp[i][j-1][0]
= piles[i] + (- diff[i+1][j]) or piles[j] + (- diff[i][j-1])
= max(piles[i] - diff[i+1][j], piles[j]- diff[i][j-1])

2D table

class Solution {
    public boolean stoneGame(int[] piles) {
        int size = piles.length;
        
        int[][] dp = new int[size][size];
        
        for(int i = size-1; i >= 0; i--) {
            // when only 1 pile left, 1st hand get stones only
            dp[i][i] = piles[i];
            // more than 1
            for(int j = i+1; j < size; j++) {
                dp[i][j] = Math.max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]);
            }
        }
        
        return dp[0][size-1] >= 0;
    }
}

[yonggui-yan]

打卡，打卡

状态 i，j，轮到1号还是2号

选择：选左还是右

1号作为先手做选择后，2号是面对新（i，j）的新手。

[Chersquwn]

大佬，两个人足够聪明，也就是先后手有影响，还是互相独立的子问题吗？为什么可以用dp？

[derainzhou]

说下我的理解, 有错误还请指教;

1.0 关于两个聪明人的博弈问题, 在代码中如何体现呢?

先手优先穷举求当前区间[i, j]下得分最大的情况;

在第一个人(先手)选择完后, 第二个就成了先手, 也会穷举当前状态下[i+1, j]或者[i, j-1]得分最大的情况;

两者身份不断交替;

Pair pair = new Pair();
Pair left = dp(memo, nums, i + 1, j);
Pair right = dp(memo, nums, i, j - 1);
// 先手先选择, 选择[i, j]区间最大得分
// 当前状态下的后手, 自然是下个状态的先手
if (left.sec + nums[i] > right.sec + nums[j]) {
    pair.fir = left.sec + nums[i];
    pair.sec = left.fir;
} else {
    pair.fir = nums[j] + right.sec;
    pair.sec = right.fir;
}

2.0 为什么能用动态规划解题, 子问题是否相互独立?

子问题是否相互独立, 还需要看dp函数的定义:

// dp(i, j)定义: nums[i...j]区间内两个博弈者的最大分数
Pair dp(int[] nums, int i, int j)

从定义上看原问题是求[i, j]区间两个玩家的最大分数, 子问题1是[i+1, j]区间的, 子问题2是[i, j - 1]区间的, 两者是完全独立的区间;

也许你认为上一轮中先手拿到了最优分, 就会影响后手就拿不到最优分;

但这完全是两个区间, 两个独立的子问题;

假设上一轮的先手对应区间是[i+1, j], 选择了nums[i+1]; 那下一轮中先手(上一轮的后手)对应的区间是[i+2, j], 两者是在不同区间求解;

[yxw007]

https://leetcode.cn/problems/stone-game/solution/ji-yi-hua-di-gui-dong-tai-gui-hua-shu-xue-jie-java/ 可以看这个题解的图，就会发现重复子问题，希望能帮助你理解。

[CarlLy7]

打卡，附上详细注解的Java代码

    class Pair {
        private int first;//先手
        private int second;//后手

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }

    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        //先对这个二维的dp数组进行一个声明：dp[i][j].first代表石子堆的索引为（i,j）的时候先手可以取到的最大石子数；dp[i][j].second代表石子堆的索引为(i,j)的时候后手可以取到的最大石子数
        Pair[][] dp = new Pair[n][n];
        //初始化，Pair数组
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                dp[i][j] = new Pair(0, 0);
            }
        }
        //base case：如果只有一个石子堆的话，先手的最大数量就是这个石子堆的数量，后手的最大石子数量就是0
        for (int i = 0; i < n; i++) {
            dp[i][i].first = nums[i];
            dp[i][i].second = 0;
        }

        //因为此时dp数组的索引和(j-1)以及（i+1）有关，所以我们从base case出发，向结果靠拢。所以从下到上，从左到右进行一个遍历
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                //如果先手先取左边的最大石子数，注意下次变成了后手
                int left=nums[i]+dp[i+1][j].second;
                //如果先手先取右边的最大石子数，注意下次变成了后手
                int right=nums[j]+dp[i][j-1].second;
                //因为这个人贼聪明，所以他肯定会选择取左边和取右边中最大石子数的那个
                if(left>right){
                    //如果取左边比取右边的石子数大的话
                    dp[i][j].first=left;
                    //这一次的后手的结果就是下一次索引从（i+1,j）的先手的最大石子数
                    dp[i][j].second=dp[i+1][j].first;
                }else{
                    //如果取右边比取左边的石子数大的话
                    dp[i][j].first=right;
                    //这一次的后手的结果就是下一次索引从（i,j-1）的先手的最大石子数
                    dp[i][j].second=dp[i][j-1].first;
                }
            }
        }
        Pair res=dp[0][n-1];
        return res.first>=res.second;
    }

[littlefattiger]

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        def helper(nums):
            n = len(nums)
            if n == 1:
                return nums[0]
            return max(nums[0] - helper(nums[1:]), nums[n-1] - helper(nums[:n-1]))
        return helper(nums) >= 0

不需要记录所有的结果， 你只需要知道你是不是能赢就可以

[sddai]

东哥，dp一定是一个上三角吗？为什么用下三角去做就会出错？

[sddai]

好像想明白了，i～j是某一轮次的结果，则其上一轮次应该是i-1～j或者i～j+1，所以是上三角。

[tohuzheng]

虽然差不多记下来了，怎么从无到有想到还是太难