Lstmxx的空间

120. 三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

链接

• 只用二维数组的情况

function minimumTotal(triangle: number[][]): number {
  const len = triangle.length;
  let dpTable = Array(len).fill(0);
  dpTable[0] = triangle[0][0];
  for(let i = 1; i < len; i++) {
    const _dpTable = Array(len).fill(0);
    _dpTable[0] = dpTable[0] + triangle[i][0];
    for(let j = 1; j < i; j++) {
      _dpTable[j] = Math.min(dpTable[j - 1], dpTable[j]) + triangle[i][j];
    }
    _dpTable[i] = dpTable[i - 1] + triangle[i][i];
    dpTable = _dpTable;
    console.log(_dpTable)
  }
  let result = dpTable[0];
  for (let i = 1; i < len; i++) {
    result = Math.min(dpTable[i], result) 
  }
  return result;
};

• 只用一维数组的情况

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