120. Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

思路: DP的经典题目,用Divide&Conquer的思路来实现,每走一步都有两个选择: 往下走跟往右走. 总体来说走下来时间复杂度有点高为O(2^n). 简单写一下用DFS实现分治的解法

public int miniPath(int[][] triangle) {
    return dfs(triangle, 0, 0);
}

public int dfs(int[][], triangle, int x, int y) {
    if (x == triangle.length - 1) {
        return 0;
    }
    int left = dfs(triangle, x + 1, y);
    int right = dfs(triangle, x + 1, y + 1);
    return Math.min(left, right) + triangle[x][y];
}

同时给下traverse的思路:

//traverse
public void dfs(int[][] triangle, int x, int y, int sum) {
    if (x == triangle.length) {
        if (sum <  miniSum) {
            miniSum = sum;
        }
        return;
    }
    dfs(triangle, x + 1, y, sum + triangle[x][y]);
    dfs(triangle, x + 1, y + 1, sum + triangle[x][y]);
}

DFS过程中, 很多点被重复计算,导致时间复杂度特别高,我们可以加cache来降低时间复杂度.
把时间复杂度降到O(n^2).

class Point {
   int x;
   int y; 
   public Point(int x, int y) {
       this.x = x;
       this.y = y;
   }
}
public int dfs(int[][], triangle, Point point, HashMap<Point, Integer> map) {
    if (point.x == triangle.length - 1) {
        return 0;
    }
    if (map.containsKey(point)) {
        return map.get(point);
    }
    int left = dfs(triangle, point.x + 1, point.y);
    int right = dfs(triangle, point.x + 1, point.y + 1);
    Point newValue =  Math.min(left, right) + triangle[point.x][point.y];
    map.put(point, newValue);
    return map.get(point);
}

我们还可以用循环DP的方式来解决这个问题:
1. Down -> Top approach
2. Top-> Down approach
对于这个题目,如果我们从底部往上开始走,每层取最小值,

1. Down -> Top approach

// 状态定义
f[i][j] 用来表示i,j出发走到最后一层的最小路径长度
n = triangle.length;
// 初始化数组
for (int i = 0; i < n; i++) {
    f[n-1][i] = triangle[n-1][i];
}
// 循环递归求解
for (int i = n - 2; i >= 0; i--) {
    for (int j = 0; j <= i; j++) {
        f[i][j] = Math.min(f[i+1][j], f[i+1][j+1]) + triangle[i][j]
    }
}
// 求结果: 起点
f[0][0]

2. Top-> Down approach

对于本题,自顶向下的方法略复杂些,主要是因为要check一些边界条件:

// 状态定义
f[i][j] 用来表示0,0出发,走到i,j的最小路径长度
n = triangle.length;
// 初始化
f[0][0] = triangle[0][0]

// 循环递归求解
for (int i = 1; i < n; i++) {
    for (int j = 1; j <= i; j++) {
        f[i][j] = OO
        if(i - 1, j 存在) {
            f[i][j] = Math.min(f[i][j], f[i-1][j]) + triangle[i][j];
        }
        if(i - 1, j - 1存在) {
            f[i][j] = Math.min(f[i - 1][j - 1], f[i][j]) + triangle[i][j]
        }
    }
}

// 求结果:
Math.min(f[n-1][0],f[n-1][1],f[n-1][2]…..);

DP的总结:

什么时候用DP来解呢? 一般有以下几个情况可以考虑用DP来做:
1. 求minimum或者maximum的问题
2. 求Yes/No的问题
3. 求个数(Count)的问题
4. 当给的条件不能sort或者swap的时候,可以考虑用DP

DP的四个要素

  1. 状态 State
  2. 转换方程Function
  3. 初始化(起点)
  4. 终点(答案)

大概面试中常见的DP类型

  1. MatrixDP(10%), 二维数组
  2. Sequence(40%), 一维数组
  3. Two Sequences DP(40%)
  4. Backpack(10%)
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s