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.

http://www.lintcode.com/en/problem/triangle/

Discussion

很简单的动归。用f[i][j]表示triang[i][j]到bottom的最短路径长度，那么状态转移方程为：
f[i][j] = min(f[i+1][j], f[i+1][j+1]) + triangle[i][j]
实现的时候需要申请O(n^2) space。
可以优化为O(n) space 一维数组，将状态转移方程转化为：
f[j] = min(f[j], f[j+1]) + triangle[i][j]

要熟练写出用一维数组的实现。和分治+hash的实现

Solution

二维数组实现。

class Solution {
public:
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    int minimumTotal(vector<vector<int> > &triangle) {
        // write your code here
        int n = triangle.size();
        if(n == 0) return 0;
        vector<vector<int> > state(n, vector<int>(n, 0));
        for(int i=n-1; i>=0; i--) {
          state[n-1][i] = triangle[n-1][i];  
        }
        for(int i = n-2; i>=0; i--) {
            for(int j=0; j<=i; j++) {
                state[i][j] = min(state[i+1][j], state[i+1][j+1]) + triangle[i][j];
            }
        }
        return state[0][0];
    }
};

一维数组实现

class Solution {
public:
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    int minimumTotal(vector<vector<int> > &triangle) {
        // write your code here
        int n = triangle.size();
        if(n == 0) return 0;
        vector<int> f = triangle[n-1];
        for(int i=n-2; i>=0; i--) {
            for(int j = 0; j<=i; j++) {
                f[j] = min(f[j],f[j+1]) + triangle[i][j];
            }
        }
        return f[0];
    }
};

如果用triangle本身替代表示状态的二维数组，则降为O(1) space

class Solution {
public:
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    int minimumTotal(vector<vector<int> > &triangle) {
        // write your code here
        int n = triangle.size();
        if(n == 0) return 0;
        for(int i = n-2; i>=0; i--) {
            for(int j=0; j<=i; j++) {
                triangle[i][j] = min(triangle[i+1][j], triangle[i+1][j+1]) + triangle[i][j];
            }
        }
        return triangle[0][0];
    }
};

无论哪个方法，自底向上的思路是一致的。在递归中这种思路非常非常普遍。

递归实现。分治的思想。time limited, O(2^n) run time. O(1) space.

class Solution {
public:
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    int minimumTotal(vector<vector<int> > &triangle) {
        // write your code here
        int n = triangle.size();
        if(n == 0) return 0;
        return helper(0,0,triangle);
    }
    int helper(int i, int j, vector<vector<int> > &triangle) {
        int n = triangle.size();
        if(i == n) {
            return 0;
        }
        int case1 = helper(i+1, j, triangle) + triangle[i][j];
        int case2 = helper(i+1, j+1, triangle) + triangle[i][j];
        return min(case1, case2);
    }
};

divide and conquer plus hash map to reduce duplicated computation. O(n^2) runtime, O(n^2) space.

class Solution {
public:
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    int minimumTotal(vector<vector<int> > &triangle) {
        // write your code here
        int n = triangle.size();
        if(n == 0) return 0;
        vector<vector<int> > hash (n, vector<int>(n, INT_MIN));
        return helper(0,0,triangle, hash);
    }
    int helper(int i, int j, vector<vector<int> > &triangle, vector<vector<int> > &hash) {
        int n = triangle.size();
        if(i == n) {
            return 0;
        }
        if(hash[i][j] != INT_MIN)//已经计算过了就不用再计算了
            return hash[i][j];
        int case1 = helper(i+1, j, triangle, hash) + triangle[i][j];
        int case2 = helper(i+1, j+1, triangle, hash) + triangle[i][j];
        hash[i][j] = min(case1, case2);
        return min(case1, case2);
    }
};

DFS。会超时。想象成有向图里面找root到最底层节点的所有路径。visited数组这里不能用来去重，因为是自顶向下，节点就是有可能重复访问。

class Solution {
public:
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    int minimumTotal(vector<vector<int> > &triangle) {
        if(triangle.empty()) return 0;
        int n = triangle.size();
        vector<vector<int> > visited(n, vector<int>(n, false));
        int result = INT_MAX;
        int path;
        dfs(triangle, 0, 0, visited, path, result);
        return result;
    }
    void dfs(vector<vector<int> > &triangle, int i, int j, vector<vector<int> > &visited, int path, int &minPath) {
        if(i == triangle.size()) {
            if(path < minPath) {
                minPath = path;
            }
            return;
        };
        //if(visited[i][j] == true) return;
        visited[i][j] = true;
        //if(i+1 == triangle.size() || visited[i+1][j] == false)
        dfs(triangle, i+1, j, visited, path + triangle[i][j], minPath);
        //if(i+1 == triangle.size() || visited[i+1][j+1] == false)
        dfs(triangle, i+1, j+1, visited, path + triangle[i][j], minPath);
    }
};