求一个动态规划算法.
一个平面中有10*10,100个格子,每个格子中有一个数字,现在从格子(0,0)出发,走到格子(9,9)(不可走斜线).问:怎么走使得经过的格子的数字之和最小?
请给出解决方案和代码...谢谢...
[解决办法]
定义一个二维数组,存放每个格子中的数组,array[i,j],再定义一个二维数组存放最小值,minArray[i,j]
minArray[i,j] = min(minArray[i-1,j],minArray[i,j-1]) + array[i,j];
用递归求一下就行了
[解决办法]
如果递归的话时间复杂度是指数级，非常不可取。请参看dynamic programming。
[解决办法]
题目说得很不清楚：
1.格子中是否有负值？
2.行走方向有要求吗？只能向右或者向上走，还是也可以沿其它方向走？
3.每个格子是否只能经过一次？还是说可以走回头路？
如果题目简化一下：从(0,0)出发后只能向右或者向上走，最终到达(9,9)
那么这时候的状态转移方程就是1L所说的“递推公式”
[解决办法]
1楼的状态转移方程没有考虑
可以回走的问题
(即默认只能向右和上方向走,(起点左下,终点右上))
实际上应该考虑存在往下回走和往左回走情况
即需要刷新所有和新加入点的关联点,
效率低了不少
[解决办法]
回走的问题可以不考率（是指一定可一回走）
若存在一个为负数的回路，那么最小距离是负无穷。
因此如果存在负数的边，那么如果题中要求回走，此题没什么意思了
负边和回走（我理解为无向图）不可能共存的。
