leetcode 486. 预测赢家 (动态规划）java

本文主要是介绍leetcode 486. 预测赢家 (动态规划）java，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.问题

给定一个表示分数的非负整数数组。 玩家1从数组任意一端拿取一个分数，随后玩家2继续从剩余数组任意一端拿取分数，然后玩家1拿，……。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

力扣（LeetCode）
原题链接;

2.方案

把玩家1，玩家2同时选完一轮后，玩家1与玩家2的分数差看做一个子问题；用dp[i][j]表示为数组的首索引为i,尾索引为j时，玩家1与玩家2最终的分数差。
循环方程： $dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])$;
然后，基础解为 i==j 时， dp[i][j] = nums[i]. 代码实现可以用递归，或者使用循环求解。

基于递归：

class Solution {public boolean PredictTheWinner(int[] nums) {int[][] dp = new int[nums.length][nums.length];int res = getDp(nums, 0, nums.length-1, dp);if(res < 0) return false;return true;}public int getDp(int[] nums, int i, int j, int[][] dp){if(i == j) return nums[i];if(i> j) return 0;dp[i][j] = Math.max(nums[i] - getDp(nums, i+1, j, dp), nums[j] - getDp(nums, i, j-1, dp));return dp[i][j];}
}

基于循环：

// improve
class Solution {public boolean PredictTheWinner(int[] nums) {int n = nums.length;int[][] dp = new int[n][n];//初始化for (int i = 0; i < n; i++) {dp[i][i] = nums[i];}//DPfor (int i = n - 1; i >= 0; i--) {for (int j = i + 1; j < n; j++) {dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);}}return dp[0][n - 1] >= 0;}
}

这篇关于leetcode 486. 预测赢家 (动态规划）java的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---