66// if(grid === null || grid.length === 0 || grid[0].length === 0){
77// return 0;
88// }
9-
9+
1010// var dp = [[]];
11-
11+
1212// dp[0][0] = grid[0][0];
13-
13+
1414// for(var i = 1; i < grid.length; i++){
1515// dp.push([]);
1616// dp[i][0] = grid[i][0] + dp[i - 1][0];
1717// }
18-
18+
1919// for(var j = 1; j < grid[0].length; j++){
2020// dp[0][j] = grid[0][j] + dp[0][j - 1];
2121// }
22-
22+
2323// for(i = 1; i < grid.length; i++){
2424// for(j = 1; j < grid[i].length; j++){
2525// var val1 = dp[i - 1][j];
2626// var val2 = dp[i][j - 1];
27-
27+
2828// dp[i][j] = Math.min(val1, val2) + grid[i][j];
2929// }
3030// }
31-
31+
3232// return dp[dp.length - 1][dp[0].length - 1];
3333// }
3434
4242var minimumTotal = function ( triangle ) {
4343var preResult = [ ] ;
4444var rows = triangle . length ;
45-
45+
4646if ( rows > 0 ) {
4747preResult . push ( triangle [ 0 ] [ 0 ] ) ;
4848} else {
4949return null ;
5050}
51-
51+
5252for ( var row = 1 ; row < rows ; row ++ ) {
5353var curResult = [ ] ;
54-
54+
5555for ( var col = 0 ; col < triangle [ row ] . length ; col ++ ) {
5656var val ;
57-
57+
5858if ( col === 0 ) {
5959val = preResult [ col ] ;
6060} else if ( col === ( triangle [ row ] . length - 1 ) ) {
6161val = preResult [ col - 1 ] ;
6262} else {
6363val = Math . min ( preResult [ col - 1 ] , preResult [ col ] ) ;
6464}
65-
65+
6666curResult [ col ] = triangle [ row ] [ col ] + val ;
6767}
68-
68+
6969preResult = curResult ;
7070}
71-
71+
7272return Math . min . apply ( null , preResult ) ;
73- } ;
73+ } ;
74+
75+
76+ //DP Solution
77+ var minPathSum = function ( grid ) {
78+ if ( grid . length === 0 ) {
79+ return 0 ;
80+ }
81+ var m = grid . length ;
82+ var n = grid [ 0 ] . length ;
83+ var paths = [ ] ;
84+
85+ // Initialize paths with 0
86+ for ( var i = 0 ; i < m ; i ++ ) {
87+ var rowtemp = [ ] ;
88+ for ( var j = 0 ; j < n ; j ++ ) {
89+ rowtemp . push ( 0 ) ;
90+ }
91+ paths . push ( rowtemp ) ;
92+ }
93+
94+ //Initialize first row
95+ paths [ 0 ] [ 0 ] = grid [ 0 ] [ 0 ] ;
96+ for ( var c = 1 ; c < n ; c ++ ) {
97+ paths [ 0 ] [ c ] = paths [ 0 ] [ c - 1 ] + grid [ 0 ] [ c ] ;
98+ }
99+ //Initialize first column
100+ for ( var r = 1 ; r < m ; r ++ ) {
101+ paths [ r ] [ 0 ] = paths [ r - 1 ] [ 0 ] + grid [ r ] [ 0 ] ;
102+ }
103+ for ( var row = 1 ; row < m ; row ++ ) {
104+ for ( var column = 1 ; column < n ; column ++ ) {
105+ var previous = Math . min ( paths [ row ] [ column - 1 ] , paths [ row - 1 ] [ column ] ) ;
106+ paths [ row ] [ column ] = previous + grid [ row ] [ column ] ;
107+ }
108+ }
109+ return paths [ m - 1 ] [ n - 1 ] ;
110+ } ;