120. Triangle

Posted on | Edited on | Views:

https://leetcode.com/problems/triangle/

Bottom up + Tabulation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//O(n) extra space
class Solution {
  public int minimumTotal(List<List<Integer>> triangle) {      
      int[] memo=new int[triangle.size()];
      int j=0;
      for(Integer x:triangle.get(triangle.size()-1)) memo[j++]=x;
      for(int layer=triangle.size()-2;layer>=0;layer--){
          for(int i=0;i<=layer;i++){
              memo[i]=Math.min(memo[i],memo[i+1])+triangle.get(layer).get(i);
          }
      }
      return memo[0];
  }
}

Recursion –> Top down + Memoizaiton

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    int[][] memo;
    private int helper(List<List<Integer>> triangle,int row,int col){
        if(row<0) return 0;
        if(col<0||col>row) return Integer.MAX_VALUE;
        if(memo[row][col]!=0) return memo[row][col];/*memo[row][col]>0 Time Limit Exceeded, but "!=" works*/
        return memo[row][col]=Math.min(helper(triangle,row-1,col-1),helper(triangle,row-1,col))+triangle.get(row).get(col);
    }
    public int minimumTotal(List<List<Integer>> triangle) {
        int min=Integer.MAX_VALUE;
        memo=new int[triangle.size()][triangle.size()];
        for(int i=0;i<triangle.size();i++){
            int res=helper(triangle,triangle.size()-1,i);
            // System.out.println(res);
            min=min<res?min:res;
        }
        return min;
    }
}
//----------------------------------------------------------------------------------------------------------------
class Solution {
  int[][] memo;
  private int helper(List<List<Integer>> triangle,int row,int col){
      if(row>triangle.size()-1) return 0;
      if(memo[row][col]!=0) return memo[row][col];/*memo[row][col]>0 Time Limit Exceeded, but "!=" works*/
      int res=Math.min(helper(triangle,row+1,col),helper(triangle,row+1,col+1))+triangle.get(row).get(col);
      memo[row][col]=res;
      return memo[row][col];
  }
  public int minimumTotal(List<List<Integer>> triangle) {
      memo=new int[triangle.size()][triangle.size()];
      int x=helper(triangle,0,0);
      return x;
  }
}

0%