算法——石子游戏（区间DP，博弈）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法——石子游戏（区间DP，博弈），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1429字，纯文字阅读大概需要3分钟。

内容图文

简介

石子游戏其实就是多人博弈，如何求最优结果。它存在很多变种，比如不同的取石方式，不同的计算输赢的方式，在这里做一个汇总。

只能从两端取

石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。
有 n 块石子排成一排。每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。
鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。
给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。
leetcode

解题思路：

• 深度优先搜索会超时，只能采用dp的思想来做；
• 首先是状态表示，用一个二维数组，表示指定区间内，先手的最大差值；
• 状态转移，当前状态就是分两种情况，拿掉左端或者右端，获得当前得分，再减去以后手的先手差值，再在左右端中取最大值；
• 这就是一个区间dp的模板题，先枚举区间长度，再枚举起点。

class Solution {
    public int stoneGameVII(int[] w) {
        int n = w.length;
        int[] s = new int[n + 1];
        // 为了在O1的时间内获取两点之间的和，这里先去前缀和
        for(int i = 1;  i <= n; i++) s[i] = s[i - 1] + w[i - 1];
        // 状态表示数组
        int[][] f = new int[n + 1][n + 1];

		// 先枚举区间长度
        for(int len = 2; len <= n; len++) {
        	// 再枚举起点
            for(int i = 1; i + len - 1 <= n; i++) {
            	// 终点
                int j = i + len - 1;
                // 状态转移，取左端点或者又端点的最大值
                f[i][j] = Math.max(s[j] - s[i] - f[i + 1][j], s[j - 1] - s[i - 1] - f[i][j -1]);
            }
        }

        return f[1][n];
    }
}

内容总结

以上是互联网集市为您收集整理的算法——石子游戏（区间DP，博弈）全部内容，希望文章能够帮你解决算法——石子游戏（区间DP，博弈）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---