动态规划 数字三角形

问题描述

在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。
三角形的行数大于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));
    }

Paste_Image.png
其实还可以再D数组上直接变换，或者用一位数组存储。此处就不写了。如有需要可以参考该博客。对我收益良多。感谢。
教你彻底理解动态规划