Dot Game and Dynamic Programming
- by Albert Diego
I'm trying to solve a variant of the dot game with dynamic programming.
The regular dot game is played with a line of dots. Each player takes either one or two dots at their respective end of the line and the person who is left with no dots to take wins.
In this version of the game, each dot has a different value. Each player takes alternate turns and takes either dot at either end of the line. I want to come up with a way to use dynamic programming to find the max amount that the first player is guaranteed to win.
I'm having problems grasping my head around this and trying to write a recurrence for the solution. Any help is appreciated, thanks!