微策略2012年校园招聘笔试题-棋盘寻宝

http://www.acmerblog.com/blog-2-1240.html
现在有一个8*8的棋盘，上面放着64个价值不等的礼物，每个小的棋盘上面放置一个礼物（礼物的价值大于0小于1000），一个人的初始位置在棋盘的左上角，每次他只能向下或向右移动一步，并拿走对应棋盘上的礼物，结束位置在棋盘的右下角，请设计一个算法使其能够获得最大价值的礼物。

简单的动态规划，最优子结构很明显。 dp[i][j]能取得的最大值，取决于dp[i-1][j],dp[i][j-1]的最大值这里对第一行和第一列单独处理，因为只能向右和向下。map[i][j] += max(map[i-1][j], map[i][j-1])

01	#include <stdio.h>

02	int map[8][8], i, j, ans;

03	int main() {

04	while (~scanf("%d", &map[0][0])) {

05	for (j = 1; j < 8; j++) {

06	scanf("%d", &map[0][j]);

07	map[0][j] += map[0][j - 1];

08

}

09	for (i = 1; i < 8; i++) {

10	scanf("%d", &map[i][0]);

11	map[i][0] += map[i - 1][0];

12	for (j = 1; j < 8; j++) {

13	scanf("%d", &map[i][j]);

14	map[i][j] += (

15	map[i][j - 1] > map[i - 1][j] ?

16	map[i][j - 1] : map[i - 1][j]);

17

}

18

}

19	printf("%d\n", map[7][7]);

20

}

21

return 0;

22

}