109.Triangle

1.Description(Easy)

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

Notice

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.

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).

2.Code

经典dynamic programming题目

解决方法：

• DFS: Traverse

• DFS: Divide Conquer

• Divide Conquer + Memorization

• Traditional Dynamic Programming

1.Traverse:要用全局变量来记录最优值，超时

2.Divided Conquer--超时

3.记忆化搜索（recursive）:Divided Conquer+ Memorization

中间很多点重复计算，去除这些，让程序记录下来结果不要做重复的事，用hash/int[][]

4.DP:时间O(n*n) ，空间 O(n*n)

Bottom up 自底向上（从(x,y)走到bottom）,最后返回最上层f[0][0].

Top Down 自顶向下 （从(0,0)走到(x,y) ）

 public int minimumTotal(int[][] triangle) {
    if (triangle == null || triangle.length == 0) {
           return -1;
       }
       if (triangle[0] == null || triangle[0].length == 0) {
           return -1;
       }

       //state:f is the min sum  from(x,y) to the bottom
       int n=triangle.length;
       int[][] f=new int[n][n];

       //Initialization:
       for(int i=0;i<n;i++){
           f[n-1][i]=triangle[n-1][i];
       }

       //function:
       for(int i=n-2;i>=0;i--){
           for(int j=i;j>=0;j--){
               f[i][j]=Math.min(f[i+1][j],f[i+1][j+1])+triangle[i][j];
           }           
      }

       return f[0][0];


    }