931. 下降路径最小和

给你一个 n x n 的方形整数数组 matrix ，请你找出并返回通过 matrix 的下降路径的最小和。

下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

链接

解析

这题很容易找出转换方程和 base case

base case

可以直接用 matrix 来做初始化 dp 数组，因为 dp 的初始值为第一行，根据转换方程，第一行的值为它本身

转换方程

0 <= i < dp.length;

0 <= j < dp[i].length;

preCol = j - 1 >= 0;

aftCol = j + 1 < dp[i].length;

dp[i][j] =
  Math.min(dp[i - 1][preCol], dp[i - 1][j], dp[i - 1][aftCol]) + dp[i][j];

function minFallingPathSum(matrix: number[][]): number {
  const dp = matrix.splice(0);
  const rowLen = dp.length;
  for (let row = 1; row < rowLen; row++) {
    const cols = dp[row];
    const colLen = cols.length;
    const preRow = row - 1;
    for (let col = 0; col < colLen; col++) {
      const pres: number[] = [];
      pres.push(dp[preRow][col]);
      const preCol = col - 1;
      const aftCol = col + 1;
      if (preCol >= 0) {
        pres.push(dp[preRow][preCol]);
      }
      if (aftCol < colLen) {
        pres.push(dp[preRow][aftCol]);
      }
      dp[row][col] = Math.min(...pres) + dp[row][col];
    }
  }
  const lastDp = dp[rowLen - 1];
  let min = lastDp[0];
  lastDp.forEach((num) => {
    min = Math.min(min, num);
  });
  return min;
}