1177-三角形-递归-java

解题思路:

注意事项:

参考代码:

import java.util.Scanner;

/**
 * @BelongsProject Demo
 * @BelongsPackage PACKAGE_NAME
 * @Author lgb
 * @CreateTime 2022-06-10  09:39
 * @Description TODO
 * @Version 1.0
 * 思路：
 * 只能向下或者向右
 * 分析出子问题：
 * 重底向上，dp[i][j] = dp[i+1][j] > dp[i+1][j+1] ? dp[i+1][j]:dp[i+1][j+1],那么最后最大的就是dp[i][j]
 * 重顶向下：dp[i][j] = dp[i-1][j] > dp[i-1][j-1] ? dp[i-1][j] : dp[i-1][j-1],那么最后在判断最下面的数组，最大的是那个
 * 边界：
 * 重底向上：+1不要越界，从下面遍历起走
 *
 *
 * 递归：
 * 有两个方向可以走，比较两个方向那个大
 * dp(i+1,j) > dp(i+1,j+1) ? dp(i+1,j):dp(i+1,j+1) + dp[i][j] = maxNumber
 */
public class dp_1177_数字三角形 {
    public static int[][] dp;
    //Integer 没初始化为null，而基本数据类型数组初始化为 0 不好在下面判断
    public static Integer[][] b;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //几组数据
        int n = scanner.nextInt();
        while (n != 0) {
            n--;
            //行
            int x = scanner.nextInt();
            //初始化
            dp = new int[x][x];
            //存储每次的最大值和下面的值相加的结果存储
            b = new Integer[x][x];
            //数据输入
            for (int i=0; i<x; i++) {
                for (int j=0; j<=i; j++) {
                    dp[i][j] = scanner.nextInt();
                }
            }
           f(0,0);
            System.out.println(b[0][0]);
        }
        scanner.close();
    }

    //递归
    public static int f(int i, int j) {
        //边界
        if (i == dp.length-1 || j == dp.length-1) {
            return dp[i][j];
        } else {
            if (b[i][j] != null) {
                return b[i][j];
            } else {
                //递推公式  dp(i+1,j) > dp(i+1,j+1) ? dp(i+1,j):dp(i+1,j+1) + dp[i][j] = maxNumber
                int f = f(i + 1, j);
                int f1 = f(i + 1, j + 1);
                b[i][j] = (dp[i][j]) +  (f > f1 ? f : f1);
                return b[i][j];
            }
        }
    }
}