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

    问题分析

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

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

    我们先来看看左上角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。

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

    1. var data=[[300,500,600,100,150],[400,100,230,160,650],[200,550,430,260,50],[100,250,330,560,250]];//数据
    2. var temp=[];//存放最优解
    3. for(var i=0;i<data.length;i++){
    4.     var unit=data[i];
    5.         temp[i]=[];
    6.     for(var j=0;j<unit.length;j++){
    7.         temp[i][j]={};
    8.         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];
    9.         if(i==0&&j==0){
    10.         }else if(i==0){//横坐标为
    11.             temp[i][j].prev={x:i,y:j-1}
    12.         }else if(j==0){
    13.             temp[i][j].prev={x:i-1,y:j}
    14.         }else{
    15.             temp[i][j].prev=temp[i-1][j].value>=temp[i][j-1].value?{x:i-1,y:j}:{x:i,y:j-1};
    16.         }
    17.     }
    18. }
    19. var t=temp[3][4];
    20. while(t.prev){
    21.     console.log('x=',t.prev.x,'y=',t.prev.y);
    22.     t=temp[t.prev.x][t.prev.y];
    23. }
    回到顶部
    我要评论

    所有评论

      相关文章