动态规划数字三角形

作者: icecrea | 来源:发表于2017-03-24 11:31 被阅读98次

动态规划 2020-03-17
动态规划合集
动态规划01
蓝桥杯动态规划练习题--数字三角形
动态规划数字三角形
动态规划数字三角形
动态规划数字三角形
数字三角形「动态规划」
动态规划之数字三角形
动态规划练习——数字三角形

问题描述

在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。
三角形的行数大于1小于等于100，数字为 0 - 99
输入格式：
5 //三角形行数。下面是三角形
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
要求输出最大和
Sample Output
30

整体思路仍然是递推求解。
用D( r, j) 来表示第r行第 j 个数字(r,j从1开始算)
用maxSum(r, j)表示从D(r,j)到底边的各条路径中，最佳路径的数字之和。maxSum(n,j)==D(n,j)本身。
因此，此题的最终问题就变成了求 MaxSum(0,0)，从(0,0)往下递归地找到(n,0)，再通过类似树形结构向上递推获得每一层不同节点的maxSum(r, j)
D(r, j)出发，下一步只能走D(r+1,j)或者D(r+1, j+1)。推出下式

if ( r == N)                  
    maxSum(r,j) = D(r,j)    
else        
    maxSum( r, j) = Max{ maxSum(r＋1,j), maxSum(r+1,j+1) } + D(r,j)

由此推出最简单的解决方案

public class test0936 {
    public static int D[][]=new int[101][101];
    public static int n;
    
    public static int maxSum(int i,int j){
        if(i==n)
            return D[i][j];
        int a=maxSum(i+1,j);
        int b=maxSum(i+1,j+1);
        return (a>b?a:b)+D[i][j];
    }
    
    public static void main(String[] args){
        
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt()-1;
        
        for(int i=0;i<=4;i++)     
            for(int j=0;j<=i;j++) {         
                D[i][j]=sc.nextInt();        
            }      
        System.out.println(maxSum(0,0));
    }
}

优化

但上面解决时间太冗余，有过多的重复计算。计算某一节点maxSum值时会重复计算下面节点的值。所以解决方法应该是保存每个节点maxSum值。

public class test0936 {
    public static int D[][]=new int[101][101];
    public static int MAXSUM[][]=new int[101][101];
    public static int n;
    
    public static int maxSum(int i,int j){
        if(MAXSUM[i][j]!=-1)//这一步通过MAXSUM存储最大值省去了重复求解过程
            return MAXSUM[i][j];
        if(i==n)
            MAXSUM[i][j]=D[i][j];
        else{
            int a=maxSum(i+1,j);
            int b=maxSum(i+1,j+1);
            MAXSUM[i][j]=(a>b?a:b)+D[i][j];
        }
        return MAXSUM[i][j];
    }
    
    public static void main(String[] args){
        
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt()-1;
        
        for(int i=0;i<=4;i++)     
            for(int j=0;j<=i;j++) {         
                D[i][j]=sc.nextInt(); 
                MAXSUM[i][j]=-1;
            }      
        System.out.println(maxSum(0,0));
    }
}

再优化

利用从底层往上推的特点对MAXSUM直接比较赋最大值其实就是将上面的方法直接转换成二维数组了思路都是不变的

public static void main(String[] args){
        
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt()-1;
        
        for(int i=0;i<=n;i++)     
            for(int j=0;j<=i;j++) {         
                D[i][j]=sc.nextInt(); 
               // MAXSUM[i][j]=-1;
            }
        for( int i = 0;i <= n; ++ i )       
            MAXSUM[n][i] = D[n][i]; 
        for( int i = n-1; i>= 0;  i-- )       
               for( int j = 0; j <= i; j++ )           
                   MAXSUM[i][j] = (MAXSUM[i+1][j]>MAXSUM[i+1][j+1]?MAXSUM[i+1][j]:MAXSUM[i+1][j+1]) + D[i][j];      
        System.out.println(MAXSUM[0][0]);
        //System.out.println(maxSum(0,0));
    }