CODEWITHSUNDEEP
algorithmdynamic-programming
Jinmae Jin
Jinmae Jin

Reputation: 19

How to approach routing path with Dynamic Programming

there is N x N sized array filled with random number (-100 <= x <= 100)

starting from A[0][0], it moves to adjacent indices by stages.

Restriction.

Can't move to visited index.

Can't go upside.

I have to get the biggest value when it finishes moving to A[N-1][N-1].

values in indices that i've visited should be added to the sum

what is the methodology to approach this problem?

[edit]

A more compact statement of a problem: given a square N*N matrix, find the maximum sum of the visited elements along any exploration path passing through adjacent nodes (no diagonals) starting from [0][0] and ending in [N-1][N-1] within the restrictions of:

Upvotes: 1

Views: 209

Answers (1)

Nico Schertler
Nico Schertler

Reputation: 32587

You need a 2D state D[i][j], which keeps track of the maximum sum just before leaving row i at column j. The first row is easy to fill - it is just the prefix sum of the matrix' first row.

For all subsequent rows, you can use the following idea: You may have left the previous row at any column. If you know the exit column of the previous row and the exit column of the current row (defined by the state you want to calculate), you know that the sum consists of the accumulated value at the previous row's exit column plus all the values in the current row between the two exit columns. And from all possible exit columns of the previous row, choose the one that results in the maximum sum:

D[i][j] = max_k (D[i - 1][k] + Sum{m from j to k} A[i][m])

Note that this sum can be calculated incrementally for all possible k. The notation Sum{m from j to k} should also be valid for k smaller than j, which then means to traverse the row backwards.

Calculate these states row by row until you end up at D[N-1][N-1], which then holds the solution for your problem.

Upvotes: 1

Related Questions