Hello everyone

**The problem:**

Given **2d** array with numbers inside each cell, you should maximize the cost to get from *top left* `(1,1)`

to *bottom right* `(N,M)`

with three paths, When you pass to cell`(i,j)`

the cost inside it *will be removed* for the next paths.

You're only allowed to move **down** or **right**.

How can I solve something like this?

I've read the tutorial here TopCoder Tutorial but I didn't understand the whole concept.

You realise that every time you move downward or to the right, either x or y is increased by 1. So after taking K steps,

`(x-1) + (y-1) = K`

.Therefore, we can represent this DP state as

`(K, x of first path, x of second path, x of third path)`

= number of apples received after the first K steps of the three paths. This is O(N^4), which fits the limit of the problem.Since each x can come from either the same x coordinate or x-1 in the previous diagonal, the transition would be:

Therefore we can solve the problem in O(N^4).

Can we use the index of row of

`x1`

so the recurrence will be:`f(y1, x1, x2, x3)`

and then we can get the other rows by`(y1+x1)`

?To be more specific, why do we use the steps number not the index of one row?

I think when K >= N, the index of the first row remains at N if I am not mistaken.

Note: you can also solve this using mincost maxflow.

Can we process the 3 path one after the other i.e. 1. find the path with max cost to get from top,left to bottom,right 2. update the cells covered by previous path as 0 (we have used up all the cost) 3. repeat #1 and #2 for second and third path

I don't think the choice of path1 affects path2 and so on, since they wouldn't intersect. What do you guys think?