坐标问题 4

思路2：可以发现，只要知道移动步数和两个横坐标，那么两个纵坐标就可以计算出来。

1. 划分阶段：每走一步为一个阶段。

与思路1不同的是，这一次两张纸条要同时移动。

2. 状态表示：设两张纸条分别位于第 r1行第 c1列、第 r2行第 c2列，i 为移动步数，那么 f(i,r1,r2)表示两张纸条从起点出发，经过 i 步分别到达这两个点时经过的数字和的最大值。

为了保证道路不交叉，应有 r1＞r2。

f(i-1,r1－1,r2－1) （↓↓）ìíf(i-1,r1－1,r2)  （↓→）

3. 状态转移方程：f(i,r1,r2)＝map(r1,c1)＋map(r2,c2)＋max f(i-1,r1,r2－1) （→↓）

îf(i-1,r1,r2) （→→）

c1＝i＋2－r1，c2＝i＋2－r2，同时 r1＋c1＝r2＋c2。

4. 输出：f(m＋n－3, m, m－1)

m＋n－3是从左上角出发，到右下角的移动步数。