题目

image.png

思路

代码

  1. //1.暴力递归
  2.     public boolean PredictTheWinner(int[] nums) {
  3.         int sum = 0;
  4.         for (int num : nums) {
  5.             sum += num;
  6.         }
  7.         return (recur(nums, 0 , nums.length - 1, true) << 1) >= sum;
  8.     }
  10.     public int recur(int[] nums, int i, int j, boolean flag) {
  11.         if (i < 0 || j < 0 || i >= nums.length || j >= nums.length || i > j) 
  12.             return 0;
  13.         flag = !flag;
  14.         if (flag)
  15.             return Math.min(recur(nums, i + 1, j, flag), recur(nums, i, j - 1, flag));
  16.         return Math.max(recur(nums, i + 1, j, flag) + nums[i], recur(nums, i, j - 1, flag) + nums[j]);
  17.     }
  19.     //2.备忘录
  20.     int[][] dp;
  21.     public boolean PredictTheWinner(int[] nums) {
  22.         dp = new int[nums.length][nums.length];
  23.         int sum = 0;
  24.         for (int num : nums) {
  25.             sum += num;
  26.         }
  27.         return (recur(nums, 0 , nums.length - 1, true) << 1) >= sum;
  28.     }
  30.     public int recur(int[] nums, int i, int j, boolean flag) {
  31.         if (i < 0 || j < 0 || i >= nums.length || j >= nums.length || i > j) 
  32.             return 0;
  33.         if (dp[i][j] != 0) return dp[i][j];
  34.         flag = !flag;
  35.         if (flag)
  36.             dp[i][j] = Math.min(recur(nums, i + 1, j, flag), recur(nums, i, j - 1, flag));
  37.         else
  38.             dp[i][j] =  Math.max(recur(nums, i + 1, j, flag) + nums[i], recur(nums, i, j - 1, flag) + nums[j]);
  39.         return dp[i][j];
  40.     }
  42.      //3.根据动态规划思路修正后的备忘录
  43.     int[][] dp;
  44.     public boolean PredictTheWinner(int[] nums) {
  45.         dp = new int[nums.length][nums.length];
  46.         return recur(nums, 0 , nums.length - 1, true) >= 0;
  47.     }
  49.     public int recur(int[] nums, int i, int j, boolean flag) {
  50.         if (i < 0 || j < 0 || i >= nums.length || j >= nums.length || i > j) 
  51.             return 0;
  52.         if (dp[i][j] != 0) return dp[i][j];
  53.         flag = !flag;
  54.         if (flag)
  55.             dp[i][j] = Math.min(recur(nums, i + 1, j, flag) - nums[i], recur(nums, i, j - 1, flag) - nums[j]);
  56.         else
  57.             dp[i][j] =  Math.max(recur(nums, i + 1, j, flag) + nums[i], recur(nums, i, j - 1, flag) + nums[j]);
  58.         return dp[i][j];
  59.     }
  61.      //4.动态规划
  62.     public boolean PredictTheWinner(int[] nums) {
  63.        int length = nums.length;
  64.         int[][] dp = new int[length][length];
  65.         for (int i = 0; i < length; i++) {
  66.             dp[i][i] = nums[i];
  67.         }
  68.         for (int i = length - 2; i >= 0; i--) {
  69.             for (int j = i + 1; j < length; j++) {
  70.                 dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
  71.             }
  72.         }
  73.         return dp[0][length - 1] >= 0;
  74.     }
  76.     //5.优化dp数组
  77.     public boolean PredictTheWinner(int[] nums) {
  78.         int length = nums.length;
  79.         int[] dp = new int[length];
  80.         for (int i = 0; i < length; i++) {
  81.             dp[i] = nums[i];
  82.         }
  83.         for (int i = length - 2; i >= 0; i--) {
  84.             for (int j = i + 1; j < length; j++) {
  85.                 dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
  86.             }
  87.         }
  88.         return dp[length - 1] >= 0;
  89.     }

预测赢家
同类型-石头游戏