三角形取数(Hard Version)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        final long INF = -1_000_000_000_000_000_000L;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        // 初始化数字三角形数组
        long[][] nums = new long[n][];
        for (int i = 0; i < n; i++) {
            nums[i] = new long[2 * i + 1];
            for (int j = 0; j < 2 * i + 1; j++) {
                nums[i][j] = sc.nextLong();
            }
        }

        // 初始化dp数组
        long[][] dp = new long[n][];
        for (int i = 0; i < n; i++) {
            dp[i] = new long[2 * i + 1];
        }

        // 数字三角形数组最后一行（n-1）行赋值
        int center = n - 1;
        for (int j = 0; j < 2 * n - 1; j++) {
            if (Math.abs(j - center) <= k) {
                dp[n - 1][j] = nums[n - 1][j];
            } else {
                dp[n - 1][j] = INF;
            }
        }

        // 从下向上递推
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= 2 * i; j++) {
                long maxNext = Math.max(dp[i + 1][j], Math.max(dp[i + 1][j + 1], dp[i + 1][j + 2]));
                if (maxNext > INF) {
                    dp[i][j] = nums[i][j] + maxNext;
                } else {
                    dp[i][j] = INF;
                }
            }
        }

        System.out.println(dp[0][0]);
    }
}