問題描述

在上面的數(shù)字三角形中尋找一條從頂部到底邊的路徑，使得路徑上所經(jīng)過的數(shù)字之和最大。路徑上的每一步都只能往左下或右下走。只需要求出這個最大和即可，不必給出具體路徑。
三角形的行數(shù)大于1小于等于100，數(shù)字為 0 - 99
輸入格式：
5 //三角形行數(shù)。下面是三角形
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
要求輸出最大和
Sample Output
30

整體思路仍然是遞推求解。
用D( r, j) 來表示第r行第 j 個數(shù)字(r,j從1開始算)
用maxSum(r, j)表示從D(r,j)到底邊的各條路徑中，最佳路徑的數(shù)字之和。maxSum(n,j)==D(n,j)本身。
因此，此題的最終問題就變成了求 MaxSum(0,0)，從(0,0)往下遞歸地找到(n,0)，再通過類似樹形結(jié)構(gòu)向上遞推獲得每一層不同節(jié)點(diǎn)的maxSum(r, j)
D(r, j)出發(fā)，下一步只能走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));
    }
}

優(yōu)化

但上面解決時間太冗余，有過多的重復(fù)計算。計算某一節(jié)點(diǎn)maxSum值時會重復(fù)計算下面節(jié)點(diǎn)的值。所以解決方法應(yīng)該是保存每個節(jié)點(diǎn)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存儲最大值省去了重復(fù)求解過程
            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));
    }
}

再優(yōu)化

利用從底層往上推的特點(diǎn) 對MAXSUM直接比較賦最大值 其實(shí)就是將上面的方法直接轉(zhuǎn)換成二維數(shù)組了 思路都是不變的

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