[Leetcode] 813. Largest Sum of Averages

813. Largest Sum of Averages

You are given an integer array nums and an integer k. You can partition the array into at most k non-empty adjacent subarrays. The score of a partition is the sum of the averages of each subarray.

Note that the partition must use every integer in nums, and that the score is not necessarily an integer.

Return the maximum score you can achieve of all the possible partitions. Answers within 10-6 of the actual answer will be accepted.

Constraints:

1 <= nums.length <= 100

1 <= nums[i] <= 10^4

1 <= k <= nums.length

Analysis:

This question asks for the an maximum value, so we usually can consider dp first.

As it is known, the key for dp is to find the transition formula. Or find the key parameters than describe an "intermediate state" completely.

The intermediate state here represents a similar question but with a smaller size.

For this question, we can try to define the state as dp[i][k], where i is the index of the elements and k is the number of subarrays.

The meaning of dp[i][k] is the maximum of average sum ending with the ith element with at most k subarrays.

Then the next step is to derive the formula to calculate the value of dp[i][k] using the previous dp with smaller values of i and k.

dp[i][k] = max(dp[x][k-1] + sum(num[x+1] to nums[i])/(i-x)), where x from 0 to i-1.

With the meaning of dp[x][k-1], the above formula is not hard to understand:

The right-hand side (rhs) enumerates all the possible ways to calculate dp[i][k], so we just need to pick up the maximum of it.

In the implementation, the boundary conditions are tricky. The thumb rule is to make sure the dp[i][k] is valid. For example, dp[i>0][0] is not valid, since there is no such case that we have non-zero elements in 0 subarray.

See the code below:

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        // dp[i][j]: the max, ending at i, up to j subarray;
        // dp[i][j] = max(dp[d][j-1] + sum(nums[d+1], ..., nums[i])/(i-d))
        // where d from j-1 to i-1.
        double res = 0;
        int n = nums.size();
        vector<double> sums(n+1, 0);
        for(int i=0; i<n; ++i) sums[i+1] = sums[i] + nums[i];
        vector<vector<double>> dp(n+1, vector<double>(k+1, 0));
        for(int i=1; i<=n; ++i) {
            for(int j=min(i, k); j>=1; --j) {
                for(int d=max(j-1, 1); d<=i; ++d) {
                    double v = (j==1&&d>1) ? 0 : (dp[d-1][j-1] + (sums[i]-sums[d-1])/(i-d+1));
                    dp[i][j] = max(dp[i][j], v);
                }
            }
        }
        return dp[n][k];
    }
};

If do not like the boundary conditions of the above dp solution, we can try dfs + memoization.

We can start from the beginning of the array, and stop to make a subarray at any possible places.

See the code below:

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<double>> memo(n, vector<double>(k, -1));
        return dfs(nums, 0, k-1, memo);
    }
private:
    double dfs(vector<int>& ns, int id, int k, vector<vector<double>>& memo) {
        // invalid ending since we cannot have more than k subarrays
        if(k<0 && id<ns.size()) return -2;
        if(id==ns.size()) return 0;
        if(memo[id][k] != -1) return memo[id][k];
        double t = 0, sum = 0;
        for(int i=id; i<ns.size(); ++i) {
            sum += ns[i];
            double v = dfs(ns, i+1, k-1, memo);
            if(v>-2) t = max(t, sum/(i-id+1) + v);
        }
        return memo[id][k] = t;
    }
};

  

Leetcode 1278: Palindrome Partitioning III

https://leetcode.com/problems/palindrome-partitioning-iii/description/

Notes:

This question is a typical dfs question, and can be optimized by memorization.

We need to continuously cut the original string into K pieces. Let say the size of the string is N, and N >= K.

If we cut at the position of the first char, then the remaining string needs to be cut into (K-1) pieces.

Now it is clear that this question becomes the same question but with a smaller size. So we can solve it recursively, or by dfs.

And also, the key parameters are the length of the string and the number of pieces to be cut.

If we use the index of the string to label the position of the starting point, then the two key parameters can be labeled as i and K.

What we need to find is memo(0, K), representing the minimum operations needed.

Once we make one cut at position i, then the total operations for this way is Operation to make string from 0 to i becomes palindrome + memo(i+1, K-1).

It is relative straightforward to find how many operation needed to make a string in palindrome.

So memo(0, K) is the smallest value from all possible cuts.

Thus, this question can be solved by dfs + memorization. (So it can also be solved by dp, which is equivalent)

So the TC of this question is O(N/K * N * K) ~ O(N^2), and SC is O(N*K).

See the code below:

class Solution {
public:
    int palindromePartition(string s, int k) {
        int n = s.size();
        vector<vector<int>> memo(n, vector<int>(k+1, -1));
        return dfs(s, 0, k, memo);
    }

private:
    int dfs(string &s, int i, int ct, vector<vector<int>> &memo) {
        if(s.size() == ct || i==s.size()) return 0;
        if(ct == 1) return find(s, i, s.size()-1);
        if(memo[i][ct] != -1) return memo[i][ct];
        int t = s.size();
        for(int j=1; i+j-1+ct<=s.size(); ++j) {
            int one = find(s, i, i+j-1);
            t = min(t, one + dfs(s, i+j, ct-1, memo));
        }
        return memo[i][ct] = t;
    }
    int find(string& s, int i, int j) {
        int res = 0;
        while(i<j) {
            if(s[i++] != s[j--]) ++res;
        }
        return res;
    }
};

Leetcoce 650: 2 Keys Keyboard

https://leetcode.com/problems/2-keys-keyboard/description/

Notes:

This question is looking for the minimum distance from one pointer to another. So in general BFS should work, but there are other ways to solve this problem as well.

There are two key two parameters: one is the value (or the length), the other is the length of pasting.

In order to code easier, below I choose dfs + memorization.

The key relation is memo[val][paste] = 1 + min(memo[val + paste][paste], memo[val][val])

Of course, we have to make sure, we will not go back directly to the original position, which means: when paste == 0, the first term in the min() will not be considered; when paste == val, the second term will not be considered.

See the code below:

class Solution {
public:
    int minSteps(int n) {
    //    if(n==1) return n;
        int val = 1, last = 0;
        vector<vector<int>> memo(n+1, vector<int>(n+1, -1));
        return dfs(val, last, n, memo);
    }
private:
    int dfs(int v, int la, int n, vector<vector<int>>& memo) {
        if(v == n) return 0; //good end
        if(v > n) return n; //dead end
        if(memo[v][la] != -1) return memo[v][la];
        int t = n;
        if(la>0) t = min(t, 1 + dfs(v+la, la, n, memo));
        if(la != v) t= min(t, 1 + dfs(v, v, n, memo));
        return memo[v][la] = t;
    }
};

The above time complexity is O(n*n), which can pass the OJ, but it ranks ~ 10%.

This question is labeled as Math, which means there may be faster ways.

After searching online, it turns out that we just need to find the prime factors of n! The arguments are listed below:

https://leetcode.com/problems/2-keys-keyboard/discuss/105928/JavaC++-Clean-Code-with-Explanation-4-lines-No-DP

It take 2 ops to double, 3 ops to triple, ...
if n % 2 == 0, then f(n) = f(n/2) + 2
if n % 3 == 0, then f(n) = f(n/3) + 3
2 * 2 = 2 + 2; 2 * 3 > 2 + 3; 4 * 4 > 4 + 4; so it is always better to divide whenever possible.
now it became a problem for finding all possible factors

See the code below:

class Solution {
public:
    int minSteps(int n) {
        if(n==1) return 0;
        for(int i=2; i<n; ++i) {
            if(n%i == 0) return i + minSteps(n/i);
        }
        return n;
    }
};

Leetcode 514: Freedom Trail

https://leetcode.com/problems/freedom-trail/description/

Notes:

In principle, this question is can be solved by brute force dfs searching: the idea is simple, we just try all the possible ways, then then find the one with the shortest steps.

The theoretical upper bound time complexity is O(N*M!), where N is the length of the ring, and M is the length of the key. So the brute method can not pass the OJ.

One improvement is that we can just memorize the results with the key parameters: one is the position on the ring, and the other is the position on the key. Since these two parameter can always give one specific state of the problem, they can be used to describe the state completely.

memo[i][j] represents the shortest step to match ring[i, .. end] to key[j, ... end].

Since we can rotate either clockwise or anti-clockwise, so for each ring[x] == key[j], we need to determine which way can give us a shorter step. This is easy to do: we just need to compare the steps from both directions, and choose the smaller one.

In one word, we will apply memorization to memorize the local minimum, and then using the local minimums to find the global minimum.

The time complexity now is O(N* N*M).

See the code below:

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int m = ring.size(), n = key.size();
        vector<vector<int>> memo(m, vector<int>(n, -1));
        return dfs(ring, 0, key, 0, memo);
    }

private:
    int dfs(string &rs, int i, string &ks, int j, vector<vector<int>>& memo) {
        if(j==ks.size()) return 0;
        if(memo[i][j] != -1) return memo[i][j];
        int temp = -1;
        for(int x=0; x<rs.size(); ++x) {
            int one_dis = 0;
            if(rs[x] == ks[j]) {
                int dis1 = abs(i - x), dis2 = (int)rs.size() - dis1;//two ways of rotation
                one_dis = min(dis1, dis2) + 1 + dfs(rs, x, ks, j+1, memo);
                if(temp == -1) temp = one_dis;
                else temp = min(temp, one_dis);
            }
        }
        return memo[i][j] = temp;
    }
};

Leetcode 1235: Maximum Profit in Job Scheduling

https://leetcode.com/problems/maximum-profit-in-job-scheduling/description/

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You're given the startTime , endTime and profit arrays, you need to output the maximum profit you can take such that there are no 2 jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

Constraints:

• 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
• 1 <= startTime[i] < endTime[i] <= 10^9
• 1 <= profit[i] <= 10^4

Notes:

The first step is that we need to sort the event or job in order.

If we sort them by the starting time, then we need to correlate the starting time with the ending time and profit.

After that, we can run a search using dfs + memorization.

The reason for memorization is to avoid re-calculate the same sub-states.

We will use memo[i] to represent the maximum profit can be gained starting with the ith job.

If we choose the ith job, we have to finish it. So the next available jobs must starts no earlier than the ith job. This gives us the start of the next search.

At current ith job position, do we need to go through all the jobs?

The answer is no. We just need to check all the jobs starting earlier than the end[i]. Why?

The logic is simple: if they start no earlier than the end[i], we just can finish the ith job first, then continue with the following jobs, which is definitely larger than that without choosing the ith job. The profit is always positive.

See the code below:

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int res = 0, len = startTime.size();
        vector<vector<int>> vs(len);
        for(int i=0; i<len; ++i) vs[i] = {startTime[i], endTime[i], profit[i]};
        sort(vs.begin(), vs.end());
        for(int i=0; i<len; ++i) {
            startTime[i] = vs[i][0];
            endTime[i] = vs[i][1];
            profit[i] = vs[i][2];
        }
        vector<int> memo(len, -1);
        return dfs(startTime, endTime, profit, 0, memo);
    }
private:
    int dfs(vector<int>& ss, vector<int>& es,vector<int>& ps,  int id, vector<int>& memo) {
        if(id <0 || id >= ss.size()) return 0;
        if(memo[id] != -1) return memo[id];
        int t = 0;
        int right = lower_bound(ss.begin(), ss.end(), es[id]) - ss.begin();
     //   cout<<right<<endl;
        for(int i=id; i<right; ++i) {
            int next_id = lower_bound(ss.begin(), ss.end(), es[i]) - ss.begin();
            t = max(t, ps[i] + dfs(ss, es, ps, next_id, memo));
        }
        return memo[id] = t;
    }
};

Leetcode 1230: Toss Strange Coins

https://leetcode.com/problems/toss-strange-coins/description/

You have some coins.  The i-th coin has a probability prob[i] of facing heads when tossed.

Return the probability that the number of coins facing heads equals target if you toss every coin exactly once.

Example 1:

Input: prob = [0.4], target = 1
Output: 0.40000

Example 2:

Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125

Constraints:

• 1 <= prob.length <= 1000
• 0 <= prob[i] <= 1
• 0 <= target <= prob.length
• Answers will be accepted as correct if they are within 10^-5 of the correct answer.

Notes:

A very nice and potentially useful programming problem!

For programming, the key is to find the state transition.

let use f(id, target) represents the probability that we can achieve starting with index of id and ending with target heads.

Then we can write:

f(id, target) = prob[i] * f(id+1, target-1) + (1 - prob[i]) * f(id+1, target).

The physical meanings for the above two parts on the right side is very obvious:

1): if the id-th gives a head with a prob[i], then the rest needs to give (target - 1) heads;

2): if the id-th gives a tail with a prob (1 - prob[i]), then the rest needs to give target heads;

In the programming point of view, in both cases, id is becomes larger, or converging to a base case. So it is programmable. In addition, following this line, we can figure out the base case.

Another important issue is the time complexity. If we run the above formula directly, it will give factorial complexity, which is too much. Actually we have re-calculated many of the sub-state. So we can use memorization to avoid this.

The optimized time complexity can be O(Len*target).

See the code below:

class Solution {
public:
    double probabilityOfHeads(vector<double>& prob, int target) {
        int len = prob.size();
        vector<vector<double>> memo(len+1, vector<double>(target+1, -1));
        return dfs(prob, 0, target, memo);
    }

private:
    double dfs(vector<double>& ps, int id, int tar, vector<vector<double>>& memo) {
        if(id<0 || tar < 0 || tar > ps.size()) return 0;
        if(id == ps.size()) {
            if(tar == 0) return 1;
            return 0;
        }
        if(memo[id][tar] != -1) return memo[id][tar];
        return memo[id][tar] = ps[id]*dfs(ps, id+1, tar-1, memo) + (1-ps[id])*dfs(ps, id+1, tar, memo);
    }
};

Lintcode 874: Maximum Vacation Days

https://www.lintcode.com/problem/maximum-vacation-days/description

Notes:

This question seems very complicated, but actually the logic to this question is very simple. Find a path with the maximum sum (or vacation days.) with some limitations.

One is that we can only move finite steps (number of the weeks), the other is that we can stay at the same node (or city).

One method is DFS + memo.

See the code below:

class Solution {
public:
    /**
     * @param flights: the airline status from the city i to the city j
     * @param days: days[i][j] represents the maximum days you could take vacation in the city i in the week j
     * @return: the maximum vacation days you could take during K weeks
     */
    int maxVacationDays(vector<vector<int>> &flights, vector<vector<int>> &days) {
        // Write your code here
        int m = flights.size(), a = days.size(), b = days[0].size();
        vector<vector<int>> g(m);
        for(int i=0; i<m; ++i) {
            g[i].push_back(i);
            for(int j=0; j<m; ++j) {
                if(flights[i][j] == 1) g[i].push_back(j);
            }
        }
        vector<vector<int>> memo(m, vector<int>(b, -1));
        return dfs(0, 0, g, days, memo);
    }

private:
    int dfs(int st, int wks, vector<vector<int>> &g, vector<vector<int>> &dys, vector<vector<int>> &memo) {
        if(wks == dys[0].size()) return 0;
        if(memo[st][wks] != -1) return memo[st][wks];
        int t = 0;
        for(auto &a : g[st]) {
            t = max(t, dys[a][wks] + dfs(a, wks+1, g, dys, memo));//find the max;
        }
        return memo[st][wks] = t;
    }
};

Leetcode 1066: Campus Bikes II

https://leetcode.com › problems › campus-bikes-ii

On a campus represented as a 2D grid, there are N workers and M bikes, with N <= M. Each worker and bike is a 2D coordinate on this grid.

We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.

The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.

Example 1:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: 6
Explanation: 
We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.

Example 2:

Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
Output: 4
Explanation: 
We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.

Note:

1. 0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
2. All worker and bike locations are distinct.
3. 1 <= workers.length <= bikes.length <= 10

Notes:

It is said that this question is from one of the onsite interviews of Google company.

The naive method is that we try all the possible combinations using backtracking, but apparently we re-calculate a lot of sub-states.

In order to better see this, let us consider two cases. One is that we let worker 1 choose bike 1, and worker 2 pick bike 2, then the rest workers choose the rest bikes (sub-state 1). The other case is that, worker 1 chooses bike 2, and worker 2 chooses bike 1, then the rest workers choose the rest bikes (sub-state 2). Apparently, sub-state 1 is the same as sub-state 2, so we just need to calculate it once, and then re-use the result directly if need it again.

To this question, bit mapping is a naturally choice to label the state. 0 represents un-used and 1 represents used. (The very small values of the number of both workers and bikes are good indicators to this.)

Since both the number of the workers and bikes are no larger than 10, an integer (32 bits) should be enough to record it. Thus, we can use two integers to memorize the combination conditions between workers and bikes. In the following code, integer state1 is for workers, and integer state2 for bikes.

Suppose there are N workers and M bikes, the total possible states is (2^N)*(2^M). So the space  complexity is O((2^N)*(2^M)). Since we only calculate once for each state, the time complexity is the same as the space complexity.

[update on 10/07/2019]: The time complexity is O(N*M*2^N*2^M), since for each substate calculation, or local minimum, we have run all the possible matches between workers and bikes.]

See the code below:

class Solution {
public:
    int minManHaDis(vector<vector<int>> &ws, vector<vector<int>> &bs) {
        int m = ws.size(), n = bs.size();//m <= n based on the question;
        vector<vector<int>> memo(1<<m, vector<int>(1<<n, -1));
        int state1 = 0, state2 = 0;
        int res = dfs(0, ws, state1, bs, state2, memo);
        //cout<<res<<endl;
        return res;
    }

private:
    int dfs(int i, vector<vector<int>> &ws, int st1, vector<vector<int>> &bs, int st2, vector<vector<int>> &memo) {
        if(i==ws.size()) return 0;//all the workers are assigned;
        if(memo[st1][st2] != -1) return memo[st1][st2];//calculated;
        int min_dis = INT_MAX;
        for(int j = 0; j < bs.size(); ++j) {//try all the bikes;
            if((st2>>j) & 1) continue;//if the bike is used;
            int one_dis = abs(ws[i][0] - bs[j][0]) + abs(ws[i][1] - bs[j][1]);
            one_dis += dfs(i+1, ws, st1 | (1<<i), bs, st2 | (1<<j), memo);//total dis in this case;
            min_dis = min(min_dis, one_dis);//min distance;
        }
        return memo[st1][st2] = min_dis;//memorize min distance;
    }
};

Leetcode 526: Beautiful Arrangement

https://leetcode.com/problems/beautiful-arrangement/description/

Notes:

This question needs backtracking. But one improvement can be added by memorization.

Let us see the code without memorization first:

class Solution {
public:
    int countArrangement(int N) {
        int res = 0, indx = 0;
        vector<int> visit(N, 0);
        dfs(indx, N, visit, res);
        return res;
    }

private:
    void dfs(int indx, int N, vector<int> &visit, int &res) {
        if(indx == N) {
            ++res;
            return;
        }
        for(int i=1; i<=N; ++i) {
            if(visit[i-1]) continue;
            if(!(i%(indx+1)) || !((indx+1)%i)) {
                visit[i-1] = 1;
                dfs(indx+1, N, visit, res);
                visit[i-1] = 0;
            }
        }
    }
};

Memorization can be applied to this question: let us think about two cases. One is that we put 1 at position 1, and 2 at position 2, and the rest are placed at positions from 3 to n. The other is that we put 2 at position 1, and 1 at position 2, and the res are placed at positions from 3 to n. So in this two cases, the state for the rest elements except 1 and 2 are the same. One of the fundamental is: for the same state, we just need to calculate once.

In this situation, we can use bit-mapping to represent the states.

See the code below:

class Solution {
public:
    int countArrangement(int N) {
        int id = 0, visit = 0;
        vector<int> memo(1<<N, -1);//for each bit, 0 means not selected, 1 selected;
        return dfs(id, N, visit, memo);
    }

private:
    int dfs(int id, int &N, int visit, vector<int> &memo) {
        if(id == N) return 1;
        if(memo[visit] != -1) return memo[visit];
        int t = 0;
        for(int i=1; i<=N; ++i) {
            if((visit>>(i-1)) & 1) continue;
            if(!(i%(id+1)) || !((id+1)%i)) {
                t += dfs(id+1, N, visit | (1<<(i-1)), memo);
            }
        }
        return memo[visit] = t;
    }
};

Leetcode 1147: Longest Chunked Palindrome Decomposition

https://leetcode.com/problems/longest-chunked-palindrome-decomposition/description/

Return the largest possible k such that there exists a_1, a_2, ..., a_k such that: Each a_i is a non-empty string; Their concatenation a_1 + a_2 + ... + a_k is equal to text; For all 1 <= i <= k, a_i = a_{k+1 - i}.

Example 1:

Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7 Explanation:
We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Notes: The first response to this question is that we need to run a recursion with dp or memo, to gradually converge to the base case. See the code below,

class Solution {
public:
    int longestDecomposition(string text) {
        int res = 1, len = text.size();
        vector<vector<int>> memo(len, vector<int>(len, -1));
        dsf(text, 0, len-1, memo);
        return memo[0][len-1];
    }

private:
    int dsf(string &ts, int x, int y, vector<vector<int>> &memo) {
        if(x<0 || y>=ts.size() || x>y) return 0;
        if(memo[x][y] != -1) return memo[x][y];
        int t = 1;
        for(int i=x; i<=(y-x+1)/2; ++i) {
            if(ts.substr(x, i) == ts.substr(y-i+1, i)) {
                t = max(t, 2 + dsf(ts, x+i, y-i, memo));
            }
        }
        memo[x][y] = t;
        return memo[x][y];
    }
};

Then later on it is found that this question can be solved directly with greedy...

See the code below,

class Solution {
public:
    int longestDecomposition(string text) {
        int len = text.size();
        for(int i=1; i<=len/2; ++i) {
            if(text.substr(0, i) == text.substr(len-i, i))
                return 2 + longestDecomposition(text.substr(i, len-2*i));
        }
        return len == 0 ? 0 : 1;
    }
};

Leetcode 1140. Stone Game II

https://leetcode.com/problems/stone-game-ii/description/


Notes:

This is a question about optimal games, so usually it is about the so-called minMax algorithm. Similar questions have been seen before frequently, like two players pick up coins optimally from an array of coins.

But for this question, they can only pick up from one side, which means one index should be enough to record the process, since the other side is always the end. The second parameter is M, or the maximum number of piles that one player can pick up.

If Alex pick up 1 pile, then the parameters becomes (1, 1) for Lee, where the first one is index and the second one is M. Then Lee can either pick one pile or two piles (if there are two piles). Then it backs to Alex.

Similarly, if Alex pick up 2 pile, then the parameters becomes (2, 2) for Lee, where the first one is index and the second one is M. Then Lee can make a choice from 1 to 4 piles (if there are enough piles). Then it backs to Alex.

The key of the minMax algorithm is that Alex will always choose the maximum among all his choices (the same as Lee), and then Lee will always leave the minimum of the rest choices to Alex when it switches back to Alex (the same as Alex leaves to Lee). 

Obviously, when one player make one move, the size the question becomes smaller and it is the still the same question. This is exactly when we can apply the recursion trick.

To reduce redundant calculation, we can choose either dp or memorization. The purpose is the same: we only need to calculation once for one case.

See the code below using memorization:

class Solution {
public:
    int stoneGameII(vector& piles) {
        int len = piles.size();
        vector> memo(len, vector(len, -1));
        dfs(piles, 0, 1, memo);
        return memo[0][1];
    }
private:
    int dfs(vector &ps, int x, int m, vector> &ms) {
        if(x>=ps.size()) return 0;
        if(ms[x][m] != -1) return ms[x][m];
        if(x+1==ps.size()) {
            ms[x][m] = ps[x];
            return ms[x][m];
        }
        int t = 0, sum = 0;
        for(int i=x; i<=min(x+2*m-1, (int)ps.size()-1); ++i) {//pay attention to boundary conditions
            sum += ps[i];
            int d = 1e6;
            for(int j=i+1; j<=min(i+1+2*max(m, i-x+1)-1, (int)ps.size()-1); ++j) {
                d = min(d, dfs(ps, j+1, max(max(m, i-x+1), j-i), ms));
            }
            if(d == 1e6) d = 0;//if there is no change of d, it means no element left
            t = max(t, sum + d);
        }
        ms[x][m] = t;
        return ms[x][m];
    }
};

Follow up question: 

How about the players can pick up piles from both sides?