http://www.lintcode.com/en/problem/triangle/
Divide and Conquer

//v 1
//O(2^n), n = triangle.length
public class Solution {
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    public int minimumTotal(int[][] triangle) {
        
        return dfs(triangle, 0, 0);
    }
    
    public int dfs(int[][] triangle, int x, int y) {
        if (x == triangle.length) {
            return 0;
        }
        
        int left = dfs(triangle, x + 1, y);
        int right = dfs(triangle, x + 1, y + 1);
        
        return triangle[x][y] + Math.min(left, right);
    }
}

traverse

v2
//O(2^n), n =triangle.length
public class Solution {
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    int best = Integer.MAX_VALUE;
    public int minimumTotal(int[][] triangle) {
        
        dfs(triangle, 0, 0, 0);
        
        return best;
    }
    
    public void dfs(int[][] triangle, int x, int y, int sum) {
       //base case 
       if (x == triangle.length) {
          if (sum < best) {
              best = sum;
          }
          return;
       }
       
       dfs(triangle, x + 1, y, sum + triangle[x][y]);
       dfs(triangle, x + 1, y + 1, sum + triangle[x][y]);
    }
}

memorization

//O(n^2)
public class Solution {
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    public int minimumTotal(int[][] triangle) {
        int[][] hash = new int[triangle.length][];
        for (int i = 0; i < hash.length; i++) {
            hash[i] = new int[i + 1];
            for (int j = 0; j < hash[i].length; j++) {
                hash[i][j] = Integer.MAX_VALUE;
            }
        }
        return dfs(triangle, hash, 0, 0);
    }
    
    public int dfs(int[][] triangle, int[][] hash, int x, int y) {
        if (x == triangle.length) {
            return 0;
        }
        if (hash[x][y] != Integer.MAX_VALUE) {
            return hash[x][y];
        }
        
        int left = dfs(triangle,hash, x + 1, y);
        int right = dfs(triangle, hash, x + 1, y + 1);
        hash[x][y] = triangle[x][y] + Math.min(left, right);
        return hash[x][y];    
    }
}

dp top down

public class Solution {
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    public int minimumTotal(int[][] triangle) {
        //initialization
        for (int i = 1; i < triangle.length; i++) {
            triangle[i][0] = triangle[i - 1][0] + triangle[i][0];
            triangle[i][i] = triangle[i - 1][i - 1] + triangle[i][i];
        }
        
        //top down
        for (int i = 1; i < triangle.length; i++) {
            for (int j = 1; j < triangle[i].length - 1; j++) {
                triangle[i][j] = Math.min(triangle[i - 1][j - 1], triangle[i - 1][j]) + triangle[i][j];
            }
        }
        
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < triangle[triangle.length - 1].length; i++) {
            min = Math.min(min, triangle[triangle.length - 1][i]);
        }
        
        return min;
    }
}