企业网站系统源码,十大摄影网站排名,网站开发简易软件,cms开发语言有哪些文章目录 题目描述问题分析程序代码 题目描述 原题链接 石子游戏中#xff0c;爱丽丝和鲍勃轮流进行自己的回合#xff0c;爱丽丝先开始 。
有 n 块石子排成一排。每个玩家的回合中#xff0c;可以从行中 移除 最左边的石头或最右边的石头#xff0c;并获得与该行中剩余石… 文章目录 题目描述问题分析程序代码 题目描述 原题链接 石子游戏中爱丽丝和鲍勃轮流进行自己的回合爱丽丝先开始 。
有 n 块石子排成一排。每个玩家的回合中可以从行中 移除 最左边的石头或最右边的石头并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时得分较高者获胜。
鲍勃发现他总是输掉游戏可怜的鲍勃他总是输所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。
给你一个整数数组 stones 其中 stones[i] 表示 从左边开始 的第 i 个石头的值如果爱丽丝和鲍勃都 发挥出最佳水平 请返回他们 得分的差值 。
问题分析
记sum[i]为前 i 个石头的值之和
状态定义dp[i][j]表示从第 i 个石头到第 j 个石头他们得分的差值
状态计算dp[i][j] max(sum[j 1] - sum[i 1] - dp[i 1][j], sum[j] - sum[i] - dp[i][j - 1])
边界条件dp[i][i] 0
程序代码
func stoneGameVII(stones []int) int {n : len(stones)sum : make([]int, n 1)dp : make([][]int, n)for i : 0; i n; i {dp[i] make([]int, n)}for i : 0; i n; i {sum[i 1] sum[i] stones[i]}for s : 2; s n; s {for i : 0; i n - s; i {j : i s - 1dp[i][j] max(sum[j 1] - sum[i 1] - dp[i 1][j], sum[j] - sum[i] - dp[i][j - 1])}} return dp[0][n-1]
}
