[LeetCode] [动态规划] Minimum Path Sum

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

问题描述：给定一个包含m*n个非负整数的网格，找到一条从左上角到右下角的路径，使得该路径上的数字的和最小。

注意：在每个点要么往下移动，要么往右移动。

本题可以采用动态规划的方法：设f(i, j)是从左上角到位置(i, j)的一条和最小的路径，那么该路径要么经过(i-1, j)，要么经过(i, j-1)，因此，最优子结构可以写为递归式：

f(i, j) = min(f(i-1, j), f(i, j-1)) + grid[i][j]，那么，可以用e[0...m-1, 0...n-1]的矩阵保存f(i, j)，又因为，e[i][j]仅依赖于e[i-1][j]和e[i][j-1]，因此，可以仅用两个数组来保存中间结果，空间复杂度为O(n)。

class Solution {  
public:  
    int minPathSum(vector > &grid) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        vector





 >::size_type grid_size = grid.size();  
  
        if(grid_size == 0)  
            return 0;  
  
        vector >::size_type arr_size = grid[0].size();  
        int *e = new int[arr_size];  
        int *tmp = new int[arr_size];  
  
        for(int i = 0; i < grid_size; ++i) {  
            for(int j = 0; j < arr_size; ++j) {  
                if(i == 0 && j == 0) {  
                    tmp[j] = grid[i][j];  
                }  
                else if(i == 0) {  
                    tmp[j] = tmp[j-1] + grid[i][j];  
                }  
                else if(j == 0) {  
                    tmp[j] = e[j] + grid[i][j];  
                }  
                else {  
                    tmp[j] = min(tmp[j-1], e[j]) + grid[i][j];  
                }  
            }  
            copy(tmp, tmp+arr_size, e);  
        }  
  
        int minsum = e[arr_size-1];  
  
        delete[] e;  
        delete[] tmp;  
  
        return minsum;  
    }  
};