下面有一个二维数组,试问如何使从左上角到右下角沿途经过的数字之和最大,注意,只能沿着向下或者向右的方向走。

background Layer 1 300 500 600 100 150 400 100 230 160 650 200 550 430 260 50 100 250 330 560 250

问题分析

这个问题最简单的就是利用深搜或者广搜找出所有结果然后对比,但是这样肯定不是最优的,这里可以考虑用动态规划,动态规划就是假设每一步都是最优的,然后导出下一步。

因为这里的只能向下或者向右走,那么对于任何一个数字而言,只能从它的左边和上边两个方向来到它这里,那么我们从两条路径中选择最优的一条就好了。

我们先来看看左上角300旁边的500和400,对于500来说,只能从左边来,最优值为800,对于400来说,只能从上边来,最优值为700。

background Layer 1 300 500 400 最优:800 最优:700

现在我们来看下左上角300斜对着的100,到100这里有两条路,一条是上面的500,一条是左边的400,因为500这条路径是最优的(刚才计算的800),所以到100这个数子,我们选择的是上方的这条路径。

background Layer 1 300 500 400 最优:800 最优:700 100 最优:900

我们可以把这种规律一直扩充下去,可以得到一个一般性的结论:

我们假设一个点的数值为value,到达它这个点的最优值为a[i,j],那么它和value的关系为:a[i,j]=max(a[i-1,j],a[i,j-1])+value。

也就是说一个点的最优值为左边来的和上边来的选大的那个。因此很容易就可以写出代码:

其他文章

0
我要评论

评论

返回
×

我要评论

回复:

昵称:(昵称不超过20个字)

图片:

提交
还可以输入500个字