算法问题1:玩家预测问题(动态规划求解)

算法问题1:玩家预测问题(动态规划求解)

玩家预测问题概述

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

举例: 输入：[1, 5, 2] 输出：False 解释：一开始，玩家1可以从1和2中进行选择。 如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。 所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。 因此，玩家 1 永远不会成为赢家，返回 False 。

提示： 1 <= 给定的数组长度 <= 20. 数组里所有分数都为非负数且不会大于 10000000 。 如果最终两个玩家的分数相等，那么玩家 1 仍为赢家

问题分析

分析: 假设当前的非负数组为nums = {2,5,1} Int n = nums.length; 我们定义一个二维数组int[][] grade = new int[n+1][n +1] i:表示数组的最左侧;j表示最右侧 grade表示玩家(1/2)作为先手在当前这个数组中所取得的最大的相对分数差 我们知道当数组只有一个元素时,显然此时无论是玩家1还是玩家2选择任意一端,其他玩家则无分数可选,则此时的最大相对分数差为此时数组元素值:即grade[i][i] = nums[i]; 接着,我们首先选择i=0,j=1的数组{2,5}: 若先手选择2,则另外一个玩家选择5:最大分数差为2-5=-3; 若先手选择5,则另外一个玩家选择2:最大分数差为5-2=3; 故真正的对于玩家1来说先手取得最大分数差为max(-3,3)=3 同理对于i=1;j=2的数组{5,1}: 取得的先手最大分数差为:max(5-1,1-5) = 4 从上面我们可以发现规律: grade[i][j] = max(nums[i] – grade[i+1][j],nums[j] – grade[i][j-1]); 分析i=0,j=2的情况: nums[0] – grade[1][2] = 2 – 4 = -2 ; nums[2] – grade[0][1] = 1 – 3 = -2; max(-2,-2) =-2 < 0;说明无论怎么选,玩家1都输了

grade[i][j] = max(nums[i] – grade[i+1][j],nums[j] – grade[i][j-1])的推导过程

因为每个玩家的玩法都会使他的分数最大化。 我们在进行计算grade[i][j]时: 若玩家1选择了nums[i]的值,则玩家2必然在前面选择了最大相对分数,即grade[i+1][j],故玩家1的最大相对分数为: nums[i] – grade[i+1][j] 若玩家1选择了nums[j]的值,则玩家2必然在前面选择了最大相对分数,即grade[i][j-1]),故玩家1的最大相对分数为:nums[j] – grade[i][j-1] 故此时玩家1的最终选择的最大相对分数为: grade[i][j] = max(nums[i] – grade[i+1][j],nums[j] – grade[i][j-1]);

java代码

package com.bingym.temp02; public class PredictWinner { /* * 动态规划解决玩家预测问题: * 给定一个表示分数的非负整数数组。 * 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。 * 每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。 * 最终获得分数总和最多的玩家获胜。给定一个表示分数的数组，预测玩家1是否会成为赢家。 * 每个玩家的玩法都会使他的分数最大化。 * 分析: * * */ public static void main(String[] args) { int[] nums = {2,5,1}; PredictWinner3 winner = new PredictWinner3(); boolean isWinner = winner.PredictTheWinner(nums); if (isWinner) { System.out.println("玩家1获胜"); }else { System.out.println("玩家1失败"); } } public boolean PredictTheWinner(int[] nums) { int n = nums.length - 1; int[][] grade = new int[n + 1][n + 1]; //首先对grade[i][i](0<= i <= n)的每个值进行赋值 for (int i = 0; i <= n; i++) { grade[i][i] = nums[i]; } //填表操作:动态规划 //因为我们需要先计算左索引大的,右索引小的的最大相对分数,后获得左索引小,右索引大的 //因为后者的最大相对分数是建立在前者的最大相对分数 for (int j = 1; j <= n; j++) { for (int i = j-1; i >=0; i--) { grade[i][j] = Math.max(nums[i]- grade[i+1][j],nums[j] - grade[i][j-1]); } } //最后:i=0,j=nums.length - 1,即为玩家1的最大相对分数 //我们将其与0进行比较:若大于0:说明玩家1可以胜出;若小于0:则说明玩家1失败 if (grade[0][n] >= 0) { return true; }else { return false; } } }