
Yes, on a first look it seems as if the solution is pretty trivial. Since we know how to calculate the maximum stars collected for a single run, let's just mark the cells from where the stars have been collected as 0. And rerun again, and similar to what we did after the previous run. mark the cells involved to 0, and then do a final third run. What we will get will be the answer! WRONG.
The approach used for a single run, tries to take a path which will maximize the total stars. But here we have the ability to run three runs. So the approach has to be cover the maximum possible number of cells using the three paths. Consider this test case, and watch the above solution fail : "0 9 8 3 4 3 4", "2 3 4 2 4 2 3", "2 3 4 2 3 4 2".
To do that the solution is pretty tough. That's why this problem is listed under Advanced category in the DP tutorial.
The breakthrough is to realize that there are three paths going from upper left corner, to lower right corner. And they all need to go through all the rows at some point of the time.
So let us have an array[50][50][50], where array[i][j][k] will depict the left path to be in column i, middle in column j, and right in column k.
Another thing is the paths must not intersect in rows 1 till n2. They can overlap in row 0 and row n1. (Use a few examples to convince yourself.)
So we begin our journey from Row 0.
array[i][j][k] where i < j < k, will be equal to sum (level[0][i]) 0<=i <= k.
Now comes the route from Row1 to row n2,
array1[i][j][k] where i<j><k = array[i][j][k] + level[1][i] + level[1][j] + level[1][k].
This depicts the movement in vertical direction of all the three paths.
But the paths may move towards right in a given row as well.
To manage that also, we need to consider 8 scenarios,
where left moves from left1 to left, but middle, and right come vertically down.
That would be array1[i][j][k] = array1[i1][j][k] + level[1][i]; other 7 cases are like, (i,m1,r) > (i,m,r), (i1,m1,r) > (i,m,r) ....Hope you are getting it. 