算法训练 数字三角形

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

public class Main {
    public static int[][] a = new int[100][100];
    public static int[][] F = new int[100][100];
    public static int n;

    public static int dp(int i, int j) {
        if (F[i][j] != 0) // F[i][j]存放从底端到到该点和的最大值
            return F[i][j];
        if (i == n - 1) // 如果到达最底端，说明走完了一条路
            F[i][j] = a[i][j];
        else // 要么从数组往下，对应原图左下，要么从数组往右下，对应原图的右下方
            F[i][j] = a[i][j] + Math.max(dp(i + 1, j + 1), dp(i + 1, j));
        return F[i][j];
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        n = cin.nextInt();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                a[i][j] = cin.nextInt();
            }
        }
        cin.close();
        System.out.println(dp(0, 0));
    }
}

类似贪心加动态规划的见我另一篇博客，其实就是百度之星的那题点击打开链接