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

问题分析

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

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

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

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

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

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

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

var data=[[300,500,600,100,150],[400,100,230,160,650],[200,550,430,260,50],[100,250,330,560,250]];//数据
var temp=[];//存放最优解
for(var i=0;i<data.length;i++){
    var unit=data[i];
        temp[i]=[];
    for(var j=0;j<unit.length;j++){
        temp[i][j]={};
        temp[i][j].value=Math.max(temp[i-1]==undefined?0:temp[i-1][j].value,temp[i][j-1]==undefined?0:temp[i][j-1].value)+data[i][j];
        if(i==0&&j==0){
        }else if(i==0){//横坐标为
            temp[i][j].prev={x:i,y:j-1}
        }else if(j==0){
            temp[i][j].prev={x:i-1,y:j}
        }else{
            temp[i][j].prev=temp[i-1][j].value>=temp[i][j-1].value?{x:i-1,y:j}:{x:i,y:j-1};
        }
    }
}
var t=temp[3][4];
while(t.prev){
    console.log('x=',t.prev.x,'y=',t.prev.y);
    t=temp[t.prev.x][t.prev.y];
}
回到顶部
我要评论

所有评论

返回
邮箱:
绑定
取消
×

我要评论

回复:

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

图片:

邮箱:
绑定邮箱后,若有回复,会邮件通知。
提交
还可以输入500个字