Minimum Path Sum

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.

 1 class Solution { 2 public: 3     int minPathSum(vector<vector<int> > &grid) { 4         5         int m=grid.size(); 6         int n=grid[0].size(); 7         8        /* int **dp=new int *[m]; 9         for(int i=0;i<m;i++)10         {11             dp[i]=new int[n];12         }13         */14        15         vector<vector<int>> dp(m,vector<int>(n));16        17         dp[0][0]=grid[0][0];18        19         for(int i=1;i<m;i++)20         {21             dp[i][0]=dp[i-1][0]+grid[i][0];22         }23        24         for(int j=1;j<n;j++)25         {26             dp[0][j]=dp[0][j-1]+grid[0][j];27         }28        29         for(int i=1;i<m;i++)30         {31             for(int j=1;j<n;j++)32             {33                 dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1]);34             }35         }36        37         return dp[m-1][n-1];38        39     }40 };