Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: Stone Game II

Posted on August 5, 2019July 26, 2020 by braindenny

Stone Game II



Similar Problems:

  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #game, #minimax, dynamicprogramming, recursive

Alex and Lee continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.

Alex and Lee take turns, with Alex starting first. Initially, M = 1.

On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.

Example 1:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

Constraints:

  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 10 ^ 4

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// https://code.dennyzhang.com/stone-game-ii
// Basic Ideas: minimax
//
//   dp(i, m): when there are piles[i:] to choose. And m is the threshold.
//   The result would be dp(0, 1) 
//
//   dp(i, j) = 
//           max(sufsum[i] - dp[i+X][max(j, X)])
//            loop: 1<=X<=2j
//
// Complexity: Time O(n^3), Space O(n^2)
/*
2, 7, 9, 4, 4

dp(0, 1) = 
    max(sufsum[0] - dp(1, 1), // take one
        sufsum[0] - dp(2, 2)) // take two
*/
func min(x, y int) int {
    if x<y {
        return x
    } else {
        return y
    }
}

func max(x, y int) int {
    if x>y {
        return x
    } else {
        return y
    }
}

func dfs(sufsum []int, i int, j int, m map[[2]int]int) int {
    if i>=len(sufsum) {
        return 0
    }
    if v, ok := m[[2]int{i, j}]; ok {
        return v
    }
    res := sufsum[i]
    v := 1<<32-1
    for k:=1; k<=2*j; k++ {
        if v == 0 {
            break
        }
        v = min(v, dfs(sufsum, i+k, max(j, k), m))
    }
    if v == 1<<32-1 {
        v = 0
    }
    res -= v
    m[[2]int{i, j}] = res
    return res
}

func stoneGameII(piles []int) int {
    m := map[[2]int]int{}
    sufsum := make([]int, len(piles))
    sum := 0
    for j:=len(piles)-1; j>=0; j-- {
        sum += piles[j]
        sufsum[j] = sum
    }
    res := dfs(sufsum, 0, 1, m)
    return res
}
linkedin
github
slack

Post Views: 0
Posted in MediumTagged #dynamicprogramming, #game, #recursive, minimax

Post navigation

LeetCode: Convex Polygon
LeetCode: Minimum Number of Taps to Open to Water a Garden

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.