HDU2084 – JAVA編程語言程序開發技術文章

[java]
package DP; 
 
//經典dp題 
/*
 * 狀態轉移方程:sum[i][j] = arr[i][j] + sum[i + 1][temp];
 * arr[i][j]初始值為 輸入的序列值
 * sum[i][j]表示第i行第j列的值為第i行第j列的原值+第i+1行中與之相連的兩個數中較大的一個和值。
 * */ 
import java.util.*; 
 
public class HDU2084 { 
        www.aiwalls.com
    public static void main(String[] args) { 
        Scanner sc = new Scanner(System.in); 
        int t, n; 
        int[][] arr, sum;// arr保存數塔序列,sum保存和值 
 
        t = sc.nextInt(); 
        while (t– > 0) { 
            n = sc.nextInt(); 
            // 初始化數組 
            arr = new int[n][n]; 
            sum = new int[n][n]; 
            // 接受輸入,初始化數塔 
            for (int i = 0; i < n; i++) { 
                for (int j = 0; j <= i; j++) { 
                    arr[i][j] = sc.nextInt(); 
                } 
            } 
             
            for(int i = 0;i<n;i++) 
                sum[n-1][i] = arr[n-1][i]; 
            // 從下往上一次求兩個相鄰的數中最大的一個與上一個數相加保存在和值數組中,則最後sum[0][0]就是最後的結果 
            for (int i = n – 2; i >= 0; i–) { 
                int temp = -1; 
                for (int j = 0; j <= i; j++) { 
                    if (sum[i + 1][j] > sum[i + 1][j + 1]) 
                        temp = j; 
                    else 
                        temp = j + 1; 
                    //狀態轉移方程 
                    sum[i][j] = arr[i][j] + sum[i + 1][temp]; 
 
                    //System.out.println(arr[i + 1][temp]); 
                } 
            } 
            System.out.println(sum[0][0]); 
 
        } 
 
    } 
 

發佈留言