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.

    void goRight(int row_index, int column_index, int **grid_sum, vector<vector<int> > &grid) {

         column_index ++ ;

         int sum = grid_sum[row_index][column_index - ] + grid[row_index][column_index];

         if(grid_sum[row_index][column_index] == - || sum < grid_sum[row_index][column_index])

             grid_sum[row_index][column_index] = sum;

     }

     void goDown(int row_index, int column_index, int **grid_sum, vector<vector<int> > &grid ) {

         row_index ++;

         int sum = grid_sum[row_index -][column_index] + grid[row_index][column_index];

         if(grid_sum[row_index][column_index] == - || sum < grid_sum[row_index][column_index])

             grid_sum[row_index][column_index] = sum;

     }

     int minPathSum(vector<vector<int> > &grid) {

         if( grid.size() <=  || grid[].size() <=){

             return ;

         }else if ( grid.size() == ){

             int sum = ;

             for (auto item : grid[])

                 sum += item;

             return sum;

         }else if (grid.size() >  && grid[].size() == ) {

             int sum =  ;

             for ( auto item : grid)

                 sum += item[];

             return sum;

         }else {

             int row_size = grid.size();

             int column_size = grid[].size();

             int  ** grid_sum = new int *[row_size];

             for( int i=; i< row_size; i++ )

             {

                 grid_sum[i] = new int [column_size]  ;

             }

             for(int i = ; i< row_size; i ++){

                 for(int j =; j < column_size; j++)

                     grid_sum[i][j] = -;

             }

             for(int i = ; i <= (row_size - + column_size -); i++) {

                 if (i == ) {

                     int row_index = ;

                     int column_index = ;

                     grid_sum[][] = grid[][];

                     if(row_index +  < row_size)

                         goDown(row_index, column_index, grid_sum, grid);

                     if(column_index +  < column_size)

                        goRight(row_index, column_index, grid_sum, grid);

                 }else {

                     int row_index = ;

                     int column_index = ;

                     for(row_index = ; row_index <= i; row_index ++ ){

                         if(row_index >= row_size )

                             continue;

                         column_index = i - row_index;

                         if(column_index >= column_size)

                             continue;

                         if(row_index +  < row_size)

                             goDown(row_index, column_index, grid_sum, grid);

                         if(column_index +  < column_size)

                             goRight(row_index, column_index, grid_sum, grid);

                     }

                 }

             }

             int sum = grid_sum[row_size - ][column_size - ];

              for( int i=; i< row_size; i++ ) {

                 delete [] grid_sum[i];

             }

             delete grid_sum;

             return sum;

         }

     }