Minimum Path Sum [LeetCode]

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Summary: DP, calucate the minimun sum from start point to every cell unitil we traverse every cell, then just output the last cell.

 1    void goRight(int row_index, int column_index, int **grid_sum, vector<vector<int> > &grid) {
 2         column_index ++ ;
 3         int sum = grid_sum[row_index][column_index - 1] + grid[row_index][column_index];
 4         if(grid_sum[row_index][column_index] == -1 || sum < grid_sum[row_index][column_index])
 5             grid_sum[row_index][column_index] = sum;
 6     }
 7     
 8     void goDown(int row_index, int column_index, int **grid_sum, vector<vector<int> > &grid ) {
 9         row_index ++;
10         int sum = grid_sum[row_index -1][column_index] + grid[row_index][column_index];
11         if(grid_sum[row_index][column_index] == -1 || sum < grid_sum[row_index][column_index])
12             grid_sum[row_index][column_index] = sum;
13     }
14     
15     int minPathSum(vector<vector<int> > &grid) {
16         if( grid.size() <= 0 || grid[0].size() <=0){
17             return 0;
18         }else if ( grid.size() == 1){
19             int sum = 0;
20             for (auto item : grid[0]) 
21                 sum += item;
22             return sum;
23         }else if (grid.size() > 1 && grid[0].size() == 1) {
24             int sum = 0 ;
25             for ( auto item : grid)
26                 sum += item[0];
27             return sum;
28         }else {
29             int row_size = grid.size();
30             int column_size = grid[0].size();
31      
32             int  ** grid_sum = new int *[row_size];
33             for( int i=0; i< row_size; i++ )
34             {
35                 grid_sum[i] = new int [column_size]  ;
36             }
37 
38             for(int i =0 ; i< row_size; i ++){
39                 for(int j =0; j < column_size; j++)
40                     grid_sum[i][j] = -1;
41             }
42             
43             for(int i = 0; i <= (row_size -1 + column_size -1); i++) {
44                 if (i == 0) {
45                     int row_index = 0;
46                     int column_index = 0;
47                     grid_sum[0][0] = grid[0][0];
48                     if(row_index + 1 < row_size)
49                         goDown(row_index, column_index, grid_sum, grid);
50                     if(column_index + 1 < column_size)
51                        goRight(row_index, column_index, grid_sum, grid);
52                 }else {
53                     int row_index = 0;
54                     int column_index = 0;
55                     for(row_index = 0; row_index <= i; row_index ++ ){
56                         if(row_index >= row_size )
57                             continue;
58                         column_index = i - row_index;
59                         if(column_index >= column_size)
60                             continue;
61                         
62                         if(row_index + 1 < row_size)
63                             goDown(row_index, column_index, grid_sum, grid);
64                         if(column_index + 1 < column_size)
65                             goRight(row_index, column_index, grid_sum, grid);
66                     }
67                 }
68             }
69 
70             int sum = grid_sum[row_size - 1][column_size - 1];
71              for( int i=0; i< row_size; i++ ) {
72                 delete [] grid_sum[i];
73             }
74             delete grid_sum;
75             return sum; 
76         }
77     }