CODEWITHSUNDEEP
algorithmdynamic-programming
Eric
Eric

Reputation: 13

Dynamic Programming "Solitare Board Game"

I have a programming problem that I am trying to work through, but I'm stuck as in which direction to begin.

The problem is as follows:

If we have some nxn square board (essentially a two-dimensional array) with each square of the grid having a numerical value in it (negative, zero, or positive). The guidelines for the game are that you may start with your "token" at any position on the board, and you can only move your token right or down (in any order). For each square you enter, you add or subtract that total from your score, and your goal is to accumulate the highest score possible before moving off any square on the right or bottom edge.

This is similar to other dynamic programming problems I've seen in the past (word aligning comes to mind), but I'm struggling with where to start without essentially taking a brute force method of dynamic programming (memoize table for each square on the right and bottom edge, but then you end up with (2n tables of size n^2, and the runtime would be atrocious).

What would you recommend as a starting point for this problem in order to achieve the highest possible score, while still keeping the algorithm as time and space efficient as possible?

Upvotes: 0

Views: 419

Answers (1)

Kisar
Kisar

Reputation: 353

If I understand this correctly, you can just make a nxn table where the entries are

table[i][j] = board[i][j] + max(table[i][j-1], table[i-1][j])

with

table[-1][j] = INT_MIN for all j

and

table[i][-1] = INT_MIN for all i

(table is the table for the maximum scores and board the actual board that you are given.)

Upvotes: 2

Related Questions