[leetcode] Minimum Path Sum

思路很简单，就是存储之前运算的结果，然后递归

class Solution {

public:

int** dp;

int

get_min_sum(vector<vector<int> > &grid, int m, int n)

{

if (dp[m][n] != -1)

return dp[m][n];

if

(m == 0 && n == 0)

return grid[m][n];

(dp[m-1][n] == -1)

dp[m-1][n] = get_min_sum(grid, m-1, n);

if (dp[m][n-1] == -1)

dp[m][n-1] = get_min_sum(grid, m,

n-1);

dp[m][n] = min(dp[m-1][n] + grid[m][n], dp[m][n-1] +

grid[m][n]);

}

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

int m =

grid.size();

int n = 0;

if (!grid.empty() &&

!grid[0].empty())

n = grid[0].size();

else

return 0;

dp =

(int**)malloc(sizeof(int*)*(m+1));

for (int i = 0; i < m+1;

++i)

dp[i] = (int*)malloc(sizeof(int)*(n+1));

for (int

i = 0; i < m+1; ++i)

memset(dp[i], -1,

sizeof(int)*(n+1));

dp[0][0] = grid[0][0];

for

(int i = 1; i < n; ++i)

dp[0][i] = dp[0][i-1] +

grid[0][i];

for (int i = 1; i < m; ++i)

dp[i][0] =

dp[i-1][0] + grid[i][0];

int res = get_min_sum(grid, m-1, n-1);

for (int i = 0;

i < m+1; ++i)

delete [] dp[i];

delete []

dp;

return res;

};