HjHimansh

StoneII

Sep 22nd, 2020
895
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.     public:
  3.     //this function returns the maximium alex can gain
  4.     typedef struct {
  5.         int maxAlex;
  6.         int maxLee;
  7.     } rt;
  8.    
  9.    
  10.     unordered_map<string, rt> memo;
  11.  
  12.     rt h_stoneGameII(vector < int > & piles, int index, int M, int chance) {
  13.         string key = to_string(index) + "|" + to_string(M) + "|" + to_string(chance);
  14.         if(memo.count(key)){
  15.             return memo[key];
  16.         }
  17.        
  18.         rt to_return;
  19.         int upperX = 2 * M;
  20.        
  21.         to_return.maxAlex = 0;
  22.         to_return.maxLee = 0;
  23.         if (piles.size() - index <= upperX) {
  24.             int sum = 0;
  25.             for (int i = index; i < piles.size(); i++) {
  26.                 sum += piles[i];
  27.             }
  28.  
  29.             if (chance == 0) {
  30.                 to_return.maxAlex = sum;
  31.                 to_return.maxLee = 0;
  32.             } else {
  33.                 to_return.maxAlex = 0;
  34.                 to_return.maxLee = sum;
  35.             }
  36.             memo[key] = to_return;
  37.             return to_return;
  38.         }
  39.        
  40.         int alexCount = 0;
  41.         int leeCount = 0;
  42.  
  43.         for (int i = index; i < index + upperX; i++) {
  44.             if (chance == 0) {
  45.                 //i.e alex is choosing
  46.                 alexCount += piles[i];
  47.                 rt maxGettingNow = h_stoneGameII(piles, i + 1, max(i-index+1, M), 1);
  48.                 if(alexCount + maxGettingNow.maxAlex > to_return.maxAlex){
  49.                     to_return.maxLee = maxGettingNow.maxLee;
  50.                     to_return.maxAlex = maxGettingNow.maxAlex + alexCount;
  51.                 }
  52.             } else {
  53.                 //i.e lee is choosing
  54.                 leeCount += piles[i];
  55.                 rt maxGettingNow = h_stoneGameII(piles, i + 1, max(i-index+1, M), 0);
  56.                 if(leeCount + maxGettingNow.maxLee > to_return.maxLee){
  57.                     to_return.maxLee = maxGettingNow.maxLee + leeCount;
  58.                     to_return.maxAlex = maxGettingNow.maxAlex;
  59.                 }
  60.             }
  61.         }
  62.         memo[key] = to_return;
  63.         return to_return;
  64.     }
  65.  
  66.     int stoneGameII(vector < int > & piles) {
  67.         return h_stoneGameII(piles, 0, 1, 0).maxAlex;
  68.     }
  69. };
RAW Paste Data