120.三角形最小路径和

链接：120.三角形最小路径和
难度：Medium
标签：数组、动态规划
简介：给定一个三角形，找出自顶向下的最小路径和。

题解 1 - typescript

• 编辑时间：2020-07-14
• 执行用时：64ms
• 内存消耗：36.8MB
• 编程语言：typescript
• 解法介绍：逆向推导[0][0],dp[i][j]=i 行 j 列时的最小步数。

function minimumTotal(triangle: number[][]): number {
  const len = triangle.length;
  const ans: number[][] = new Array(len + 1);
  ans[len] = new Array(len + 1).fill(0);
  for (let i = len - 1; i >= 0; i--) {
    const arr: number[] = [];
    for (let j = 0, l = triangle[i].length; j < l; j++) {
      arr[j] = Math.min(ans[i + 1][j], ans[i + 1][j + 1]) + triangle[i][j];
    }
    ans[i] = arr;
  }
  return ans[0][0];
}

题解 2 - typescript

• 编辑时间：2020-07-14
• 执行用时：76ms
• 内存消耗：37MB
• 编程语言：typescript
• 解法介绍：根据题解 1，利用滑动数组来节省空间。

function minimumTotal(triangle: number[][]): number {
  const len = triangle.length;
  const ans: number[][] = new Array(2);
  ans[len % 2] = new Array(len + 1).fill(0);
  for (let i = len - 1; i >= 0; i--) {
    const arr: number[] = [];
    for (let j = 0, l = triangle[i].length; j < l; j++) {
      arr[j] = Math.min(ans[(i + 1) % 2][j], ans[(i + 1) % 2][j + 1]) + triangle[i][j];
    }
    ans[i % 2] = arr;
  }
  return ans[0][0];
}

题解 3 - typescript

• 编辑时间：2021-09-03
• 执行用时：80ms
• 内存消耗：39.7MB
• 编程语言：typescript
• 解法介绍：动态规划。

function minimumTotal(triangle: number[][]): number {
  const n = triangle.length;
  for (let i = n - 2; i >= 0; i--)
    for (let j = 0; j <= i; j++)
      triangle[i][j] += Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
  return triangle[0][0];
}