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

**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) —

**GD Star Rating***loading…*

608 words

**Last Post**: Teaching Kids Programming – Single Source Shortest Path Algorithm in a Directed Unweighted Graph using Breadth First Search **Next Post**: Function to Return the USDT/USDD/USDC Contract Address on Tron Blockchain (Main Net, Nile, Shasta)

Source: Internet