Finding the Path via Memoization
Finding the actual path is also easy. All we need is an additional matrix, which stores the predecessor for each cell (r, c) when finding the maximum path. For example, in the figure above, when filling (1, 1), the maximum reward would be 8+5 when the predecessor in the path is the cell (0, 1). We need one additional matrix d that gives us the direction of the predecessor:
SNIPPET
1d[r,c] = coordinates of the predecessor in the optimal path reaching `[r, c]`. Here is the translation:
1// d[r,c] = coordinates of the predecessor in the optimal path reaching `[r, c]`.The pseudo-code for filling the direction matrix is given by the attached pseudocode.
SNIPPET
1Routine: bestDirection
2routine will fill up the direction matrix
3Start cell coordinates: (0,0)
4Goal cell coordinates: (m-1,n-1)
5Input: Reward matrix w
6
7Base case 1:
8// for cell[0,0]
9d[0,0] = (-1, -1) //not used
10
11Base case 2:
12// zeroth col. Can only move up
13d[r,0] = (r-1, 0) for r=1..m-1
14
15Base case 3:
16// zeroth row. Can only move right
17reward[0, c] = d[0,c-1] for c=1..n-1
18
19Recursive case:
201. for r=1..m-1
21 a. for c=1..n-1
22 i. if reward[r-1,c] > reward[r,c-1])
23 then d[r,c] = (r-1, c)
24 else
25 d[r,c] = (r, c-1)
262. return dxxxxxxxxxx30
return d;// Routine: bestDirection// Routine will fill up the direction matrix// Start cell coordinates: (0,0)// Goal cell coordinates: (m-1,n-1)// Input: Reward matrix w​// Base case 1:// For cell[0,0]d[0,0] = new int[] {-1, -1}; //not used​// Base case 2:// Zeroth col. Can only move upfor (int r=1; r<m; r++) d[r,0] = new int[] {r-1, 0};​// Base case 3:// Zeroth row. Can only move rightfor (int c=1; c<n; c++) d[0,c] = d[0,c-1];​// Recursive case:for (int r=1; r<m; r++) { for (int c=1; c<n; c++) { if (w[r-1,c] > w[r,c-1]) d[r,c] = new int[] {r-1, c}; else d[r,c] = new int[] {r, c-1}; }}OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment