SOURCE: LeetCode problem (#1140)

Alex and Lee play a game with piles of stones. There are several piles arranged in a row and each pile has a positive integer number of stones (piles[i]). The objective of the game is to maximize the number of stones Alex can get.

Here is a JavaScript solution using dynamic programming (DP)¹. This problem is solved recursively with memoization***². We'll create a 2D DP array³***, dp, to save the maximum number of stones Alex can get. The state is determined by two variables: i is the current pile index, and M is the maximum number of piles Alex can take.

/**
 * @param {number[]} piles
 * @return {number}
 */
var stoneGameII = function(piles) {
    const n = piles.length; 
    const dp = Array.from({length: n}, () => new Array(n).fill(0));
    const sum = new Array(n).fill(0); 
    sum[n - 1] = piles[n - 1];

    // Precalculate the sum of the stones from the i^th pile to the end of the array.
    for (let i = n - 2; i >= 0; i--) {
        sum[i] = sum[i + 1] + piles[i];
    }

    // Start the DP function
    return dpHelper(0, 1);

    function dpHelper(i, M) {
        if (i >= n) {
            return 0;
        }
        if (2 * M + i >= n) {
            return sum[i];
        }
        if (dp[i][M] !== 0) {
            return dp[i][M];
        }
        let min = Number.MAX_SAFE_INTEGER;

        // Try all possible X starting from 1 to 2*M and choose the one which results in a minimal value for Lee.
        for (let X = 1; X <= 2 * M; X++) {
            min = Math.min(min, dpHelper(i + X, Math.max(M, X)));
        }

        // The maximum stones Alex can get is the total stones minus the minimal value for Lee.
        dp[i][M] = sum[i] - min;
        return dp[i][M];
    }
};

This function stoneGameII accepts a list piles of stones as input and returns the maximum number of stones Alex can get. This function utilizes dynamic programming to optimize the time complexity to O(n^3), where n is the number of piles.

The dynamic programming array dp[i][M] is used to store the maximum number of stones that Alex can get starting from the i***^th*** pile with the maximum M piles that Alex can take. dpHelper(i, M) is a helper function to calculate dp[i][M].

The variable sum[i] stores the total number of stones from the i***^th*** pile to the end, which helps calculate the number of stones Alex can get quickly.

For each i and M, we try to find the minimum number of stones that Lee can get (stored in min) for all possible X that Alex can take. Because Alex tries to maximize the number of stones he can get, and the total number of stones is sum[i], the number of stones that Alex can get is sum[i] - min, which is stored in dp[i][M].

Footnotes:

1. Dynamic Programming (DP): Dynamic programming is a method for solving complex problems by breaking them down into simpler, overlapping subproblems, solving each of those subproblems just once, and storing their solutions in case the next time the same subproblem occurs. The main idea behind DP is using past knowledge to make future decisions. It is often used when the problem can be divided into overlapping subproblems, and it combines their solutions to get the solution for the main problem.

2. 2D DP array: In the context of dynamic programming (DP), a 2D DP array is a two-dimensional array used to store intermediate results for subproblems. Each entry in the array typically represents a state of the problem. This array is filled in a systematic way such that larger subproblems can be solved using the solutions to smaller subproblems. In the given code, dp[i][M] is a 2D DP array storing the maximum number of stones Alex can get starting from the i***^th*** pile and can take up to M piles.

3. Recursion with Memoization: Recursion is a programming pattern where a function calls itself to solve a smaller instance of the same problem. It's often used in problems where a structure can be defined in terms of itself. In many recursive problems, the same subproblems are calculated multiple times which is inefficient. Memoization is a technique used to optimize such recursive functions by storing the results of expensive function calls (results of subproblems) and reusing them when the same inputs occur again. This can significantly improve the performance of the function by eliminating the repeated calculation of the same subproblems. In the context of this problem, memoization is applied in the helper function dpHelper(i, M) where previously calculated maximum number of stones Alex can get, dp[i][M], is stored and reused when needed.

Jon Christie

jonchristie.net