题解 | 三角形取数(Hard Version) c#

using System;
using System.Collections.Generic;
using System.Linq;
public class Program {
    public static void Main() {
        int[] inputs = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        int n = inputs[0];
        int k = inputs[1];
        List<List<long>> triangle = new List<List<long>>();
        for (int i = 0; i < n; i++) {
            triangle.Add(Console.ReadLine().Split(' ').Select(long.Parse).ToList());
        }
        Console.WriteLine(getNumberFromTriangle(n, k, triangle));
    }

    public static long getNumberFromTriangle(int n, long k,
            List<List<long>> triangle) {
        long maxCalculation = 0;
        long INF =
            -1_000_000_000_000_000_000L;//INF（负无穷）就是一个“标记”，用来表示“这个位置无法到达合法终点”。
        //这道题是有办法求出走到最后一列的合法列是哪些（最后一行哪些位置 (n-1, j) 是合法终点，即存在一条路径使得 |L - R| ≤ k），设向左下移动 L 次，向右下移动 R 次，正下移动 M 次 总步数：L + R + M = n - 1，但是注意这里的“左下”和“右下”是相对于三角形结构的，列号增加的方向任然是向右！每次左下：列号不变，每次右下：列号 +2 每次正下：列号 +1。 所以最终的列号是j = 0 + 0*L + 1*M + 2*R = M + 2R, 又因为L + M + R = n -1 总步数，最终根据一系列计算得出|j - (n-1)| ≤ k
        //这次用的是从下往上的动态规划
        long[][] dp = new long[n][];
        //初始化dp
        for (int i = 0; i < n; i++) {
            dp[i] = new long[2 * i + 1];
        }

        //初始化最后一行
        int center = n - 1; //每一行的中间都是其长度-1
        for (int j = 0; j < 2 * n - 1; j++) {
            if (Math.Abs(j - center) <= k) {
                dp[n - 1][j] = triangle[n -
                                        1][j]; //符合|j - (n-1)| ≤ k的位置说明是合法位置
            } else {
                dp[n - 1][j] = INF; //给不合法位置赋值无穷小
            }
        }
        //从下往上递推
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= 2 * i; j++) {
                //从倒数第二行开始计算dp，此时每个位置的dp的值应为下一行能走的三个位置中的最大值 + 当前位置的值
                long maxVakueFromNextLine = Math.Max(dp[i + 1][j], Math.Max(dp[i + 1][j + 1],
                                                     dp[i + 1][j + 2]));
                if (maxVakueFromNextLine !=
                        INF) { //如果最大值不为无穷小，说明此位置可走向下一行的合法位置，所以此位置也是合法位置
                    dp[i][j] = triangle[i][j] + maxVakueFromNextLine;
                } else {
                    dp[i][j] = INF;//不是合法位置
                }
            }
        }
        return dp[0][0];

    }
}