坐标问题 1

(1) 单向取数问题

【问题描述】一个 m×n 的方格，每个格子都有一个数字。现在从方格的左上角出发，到右下角停止。要求只

能往右走或往下走，且一次只能走一步。现在使经过的所有数字的和最大，问最大值是多少？（1≤m,n≤1000）

1	5	9	8	2
8	6	4	7	3
7	2	5	1	6
1	0	1	4	3

【分析】

很容易想到贪心算法，即每次往数值更大的方向走。不过它是错误的。正确的做法是动态规划：

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

2. 状态表示：f(r,c)表示从起点出发走到第 r 行第 c 列时经过数字总和的最大值。

ì

3. 状态转移方程：f(r,c)＝maxíf(r-1,c)＋map(r,c)

îf(r,c-1)

边界处理：让方格的下标从1开始，这样方格就可以多出一圈——0。

(2) 变式问题

① 必须经过某点

解决方法：将取数过程分成两部分。第一部分的起点是(1,1)，终点是这个点；第二部分的起点是这个点，终点是(m,n)（第 m 行第 n 列）。比如，要求必须过(3,2)，就可以按下图把问题一分为二：

	1		5		9		8		2
	8		6		4		7		3
	7		2		5		1		6
1		0		1		4		3

② 不能经过某点

一个简单的办法是：把那个点的值设置成－INF（负无穷大）。由于经过此点要“付出巨大的代价”，所以状态不会从这点转移而来。

③ 竖直方向上最多有连续两个点相邻

解决方法：在状态中加一维，表示“已经连续向下走的次数”。

1. 状态表示：f(r,c,i)表示从起点出发走到第 r 行第 c 列时经过数字总和的最大值，i 表示“已经连续向下走的次数”。

ìf(r,c-1,0)

2. 状态转移方程：f(r,c,0)＝maxí ＋map(r,c)

îf(r,c-1,1)

f(r,c,1)＝f(r-1,c,0)＋map(r,c)

3. 输出：f(m,n,0)和 f(m,n,1)中的最大值。