三つな道を最適に選ぶ問題

最近トップコーダーの代表的な動的計画法問題を解こうとしています。　皮肉的な事で動的計画法を使わない方が良さそうです。　The problem involves finding a sequence of three traversals between the upper left and lower right corners of a grid such that, given that items are collected upon the first visit to a square and the number of items available is given as an input matrix, the optimal number of items can be collected. The single-path case is straightforward, involving dynamic programming on the optimal value up to the (i,j) index. For three such paths, a key insight is that no two paths need cross, so the dp array can be in four dimensions on the row, rightmost column of left path, rightmost column of center path, and rightmost column of right path. Given an index (y,i,j,k), it can be reached from 4 different predecessors:
(y-1,i,j,k)
(y,i-1,j,k)
(y,i,j-1,k)
(y,i,j,k)
Thus the dp transition considers the transition maximizing the total value. This update is iterated over all y, i, j, and k values, and is thus O(n^4).
In a "down" move, three new squares' contents are added to the total, whereas in a "right" move, at most one new squares' contents are added.
However, a recurrent transition function from dp[i-1][j][k] to dp[i][j][k] which avoids double-counting the A[y][i] content amounts in all cases has yet to be discovered.
The key insights seem to be the following:
1. Instead of a backward-looking dynamic programming approach, a forward-looking recursion approach seems more appropriate.
2. If a backwards iteration from the lower right to the upper left is carried out, it is possible to use dynamic programming to process the search. Note, in fact, that such a dynamic programming approach fails, as double-counting again occurs.
3. The number of steps used by all three paths is identical, as all must start and end at the same square.
The correct solutions use a four-dimensional dynamic programming data structure which is somewhat cryptic. A six-dimensional recursion on the x and y coordinates of the end points of the three paths makes sense, but how this is reduced to four dimensions is unclear.
The key to solving this problem is the notion of time steps. For a given time step t, all paths have moved t squares. Thus, the row number r of each path's endpoint is uniquely determined by the column number c and the time step t, ie r=t-c. The problem can then be modeled in state space using a dynamic programming array on (time,col1,col2,col3). This is O(2*n^4), which is likely tractable. Also, no double counting can occur as, if col1 is 1 and t is 2, row1 is 1. The grid value for (1,1) can only be added into the solution at t=2, and, as long as we do not count for identical values of col1 and col2 or col3, will not be added into the dp[t][c1][c2][c3] array twice. dp[t][c1][c2][c3] will consider the optimal step from dp[t-1][c1'][c2'][c3'] and the number of stars in the endpoints. This approach works, provided that the runtime allocates a stack size exceeding 50mb, which in gcc is accomplished via the -Wl,--stack,67108846 linker flag for a 64MB stack. An alternative is to declare the dynamic programming data structure as int****dp and use a triple for loop to allocate on the heap with new and free with delete.