P208 三角形中的最小路径和

描述#

这个题目说的是，给你一个数字三角形，你要找到从上到下路径和最小的一条路径，然后返回这个最小的路径和。

注意，每一次你只能移动到下一行相邻的两个数字上。

比如说，给你的数字三角形 a 是：
[
[1],
[2,3],
[4,5,1],
[6,1,1,8]
]
在这个三角形中，路径和最小的路径是 [1,3,1,1]。它的和等于 6。因此，你要返回的最小路径和就是 6。

相关视频：最小路径和

代码#

public class AlgoCasts {

  // Time: O(n^2), Space: O(n^2)
  public int minimumTotalTopDown(List<List<Integer>> a) {
    int n = a.size();
    int[][] d = new int[n][n];
    d[0][0] = a.get(0).get(0);

    for (int i = 1; i < n; ++i) {
      d[i][0] = d[i-1][0] + a.get(i).get(0);
      d[i][i] = d[i-1][i-1] + a.get(i).get(i);
      for (int j = 1; j < i; ++j) {
        d[i][j] = Math.min(d[i-1][j-1], d[i-1][j]) + a.get(i).get(j);
      }
    }
    int min = d[n-1][0];
    for (int i = 1; i < n; ++i)
      min = Math.min(min, d[n-1][i]);
    return min;
  }

  // Time: O(n^2), Space: O(n)
  public int minimumTotalTopDownOn(List<List<Integer>> a) {
    int n = a.size();
    int[] d = new int[n];
    d[0] = a.get(0).get(0);

    for (int i = 1; i < n; ++i) {
      int pre = d[0];
      d[i] = d[i-1] + a.get(i).get(i);
      d[0] = d[0] + a.get(i).get(0);
      for (int j = 1; j < i; ++j) {
        int tmp = d[j];
        d[j] = Math.min(pre, d[j]) + a.get(i).get(j);
        pre = tmp;
      }
    }
    int min = d[0];
    for (int i = 1; i < n; ++i)
      min = Math.min(min, d[i]);
    return min;
  }

  // Time: O(n^2), Space: O(n^2)
  public int minimumTotalBottomUp(List<List<Integer>> a) {
    int n = a.size();
    int[][] d = new int[n][n];
    for (int j = 0; j < n; ++j)
      d[n-1][j] = a.get(n-1).get(j);
    for (int i = n-2; i >= 0; --i)
      for (int j = 0; j <= i; ++j)
        d[i][j] = Math.min(d[i+1][j], d[i+1][j+1]) + a.get(i).get(j);
    return d[0][0];
  }

  // Time: O(n^2), Space: O(n)
  public int minimumTotalBottomUpOn(List<List<Integer>> a) {
    int n = a.size();
    int[] d = new int[n];
    for (int j = 0; j < n; ++j)
      d[j] = a.get(n-1).get(j);
    for (int i = n-2; i >= 0; --i)
      for (int j = 0; j <= i; ++j)
        d[j] = Math.min(d[j], d[j+1]) + a.get(i).get(j);
    return d[0];
  }

}