算法题，用动态规划求NXN方格里面用户走过的最大值。

用动态规划求在N X N 的方格中每个方格具有不同的值。这些值可以是正的也可以是负的。
用户随便选择其中一点作为起始点可以上下左右任意移动，当抵达边界的时候游戏结束。然后统计用户经过路径的值得和。
比如说
-1 7 -8 10 -5
-4 -9 8 -6 0
5 -2 -6 -6 7
-7 4 7 -3 -3
7 1 -6 4 -9

在这个方格中用户经过了 8 ， -6 ， 7 ，-3 ，4
所以最终值是8-6+7-3+4 = 10
请问下这个问题用动态规划怎么求啊。
这个问题的英文名字叫Vankin’s Mile 我找了没找到答案
下面这个网址有分析的但是没看懂
http://www.geeksforgeeks.org/forums/topic/microsoft-interview-question-for-software-engineerdeveloper-fresher-about-algorithms-11/
小弟冰天雪地跪求了

6 个解决方案

#1

你发的题目和那个链接里的题目不一样。你说的是上下左右都可以，链接里只允许右或下
因此，你的问题没有什么好方法。而链接里说只允许右下的话，这是so基础的动态规划。

#2

SO基础啊还是不知道怎么解呢
好吧我看错了是想例子里面说的向下和向右
这个要怎么解呢？

#3

有人帮看下么？

#4

如果只能右和下那就简单了,晚上给你代码,白天不好班上不好写.

#5

这个题目,还有有点犯迷糊,这到底是不是找出值最大的一条路.但是按照下面给出的答案,明显只有超出当前1步的最优值.题目下面也写了,This is not the best possible score for these values.

如果要找出最大的一条路径,必须循环,而且模型还是蛮复杂的.

#6

这道题目显然是一个动态规划问题，可能在O（n^2)的时间内完成，状态转移方程很重要，处理好边界就行

#1

#2