Hdu 2084 数塔问题

Question

就是从求最小路径和变成求最大路径和，思想没变。

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    // 方法一: 记忆化递归
    static int maxPath(int[][] matrix, int n) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return 0;
        int[][] map = new int[n][n]; //注意这里 
        return rec(matrix, 0, 0, n - 1, map);
    }
 
    static int rec(int[][] matrix, int r, int c, int n, int[][] map) {
        if (r == n)
            return matrix[r][c];

        if (map[r][c] != 0)
            return map[r][c];

        map[r][c] = matrix[r][c] + Math.max(rec(matrix, r + 1, c, n, map),
                rec(matrix, r + 1, c + 1, n, map)
        );

        return map[r][c];
    }


    // 二维 dp
    static int maxPath2(int[][] matrix, int n) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return 0;
        int[][] dp = new int[n][n]; 

        for (int j = 0; j < n; j++)
            dp[n - 1][j] = matrix[n - 1][j];

        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = matrix[i][j] + Math.max(dp[i + 1][j], dp[i + 1][j + 1]);
            }
        }
        return dp[0][0];
    }

    //一维 dp
    static int maxPath3(int[][] matrix, int n) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return 0;
        int[] dp = new int[n];

        for (int j = 0; j < n; j++)
            dp[j] = matrix[n - 1][j];

        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {// 不能写出 for(int j = i ; j >= 0; j--)
                dp[j] = matrix[i][j] + Math.max(dp[j], dp[j + 1]);
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int C = cin.nextInt();
        while (C-- > 0) {
            int n = cin.nextInt();
            int[][] matrix = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j <= i; j++) {
                    int x = cin.nextInt();
                    matrix[i][j] = x;
                }
            }
//            System.out.println(maxPath(matrix,  n));
//            System.out.println(maxPath2(matrix, n));
            System.out.println(maxPath3(matrix, n));
        }
    }
}