Teaching Kids Programming – Minmax Dynamic Programming Algorithm (Game of Picking Numbers at Two Ends)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of integers candies and are racing to collect the most amount of candies against a friend. The race is turn based, with you starting first, and in each round you can pick up candies from the front or from the back.

Return whether you can collect more candies than them.

Constraints
n ≤ 1,000 where n is the length of candies
Example 1
Input
candies = [1, 3, 2, 6]
Output
True
Explanation
You can pick up 6 candies in the first round and regardless of whether Lawrence picks 1 or 2, you can win by taking any remaining candy.

Example 2
Input
candies = [1, 10, 1]
Output
False
Explanation
Whether you pick up from front or from the back, Lawrence can pick up 10 candies and win the race.

Hints:
Both players have to choose in such a way that he/she wins. In other words, both players try to minimize the score of the other player.
Did you hear about min-max dp?

Minmax Dynamic Programming Algorithm (Game of Picking Numbers at Two Ends)

This is a classic Two Player Zero Sum Game. One player aims maximizing the scores/numbers, and the other minimizes the numbers. Each player has two choices: picking first number or the last. Thus the search process can be visualized as a MinMax Tree.

We can implement a Top Down Minmax Dynamic Programming Algorithm using Recursion with Memoziation. Let f(i, j) represent the max score (if positive, then we can win) to pick among numbers at P[i..j]. Then we can bruteforce two choices picking the first number or the last number – the result being the max of both.

Since the opponent is minimizing, we need to negate the score when we do the Recursion. The time/space complexity is O(N^2) as we are using cache and the number of the states is N*N.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def minMaxDP(self, P):
        @cache
        def f(i, j):
            if i == j:
                return P[i]
            return max(
                P[i] - f(i + 1, j), P[j] - f(i, j - 1)
            )
        return f(0, len(P) - 1) > 0

class Solution:
    def minMaxDP(self, P):
        @cache
        def f(i, j):
            if i == j:
                return P[i]
            return max(
                P[i] - f(i + 1, j), P[j] - f(i, j - 1)
            )
        return f(0, len(P) - 1) > 0

We can use the Bottom Up Dynamic Programming to solve this as well.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def minMaxDP(self, P):
        n = len(P)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = P[i]
 
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = max(P[i] - dp[i + 1][j], P[j] - dp[i][j - 1])            
        
        return dp[0][-1] > 0

class Solution:
    def minMaxDP(self, P):
        n = len(P)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = P[i]

        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = max(P[i] - dp[i + 1][j], P[j] - dp[i][j - 1])            
        
        return dp[0][-1] > 0

–EOF (The Ultimate Computing & Technology Blog) —