Just write to mark for personal reference purpose
>>>>>>>>>>
一个 m x n 二维区域,每个点上有一定数量的钱,考虑路径 : 从坐下角
(m-1, 0)出发,终点是 右上角(0, n-1), 在每个点只能向右或者向上走,
现在有两个人,从起点出发,走到终点,问怎么样求出这两个人能拿到
的钱的和的最大值
>>>>>>>>>>
(1) Find one single optimal path P which contains m+n point
(2) For each point (i,j), (k,h) in P, denoting P((i,j)->(k,h)) as the path
connecting 2 points in P, there is one property
* For all the possible paths between (i,j) and (k,h), the P((i,j)->(k,h)) is
optimal.
(3) For this problem, the solution may be 2 possible cases(the 2 paths
should not collide at any point)
<1> P + optimal path for either the upper part or lowe part split by the
optimal path (this one is easy)
<2> It's obvious that the final solutions P1 and P2 must each collide with P
on some parts(otherwise, case 1 will be always better than this). Given
property *, the final 2 paths should be like this: WLOG, P1 will collide
with P on the beginning part, and P2 will collide with P on the endin part,
and these 2 colliding parts don't necessarily cover the whole P.
So, the answer will be for each point (i,j) in P, in the upper part and
lower part split by P, find the optimal path from (m,0)->(i,j) and (i,j)->(0
,n); And then find out the pair (i1,j1), (i2,j2)in P that give the optimal
of
P((m,0)->(i1,j1))+Pupper((i1,j1)->(0,n))+Plower((m,0)->(i2,j2))+P(i2,j2)->(0
,n))
or
Pupper((m,0)->(i2,j2))+P((i2,j2)->(0,n))+P((m,0)->(i1,j1))+Plower((i1,j1)->(
0,n))
assuming (i1,j1) is before (i2,j2) in P.
Total time will be O(mn)+O(m2)+O(n2)