pic

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.

分析

  题目的意思是，给定一个m*n的格子，每个格子有一个非负整数，找一条从左上到右下的路线，使这条路线经过的整数和最小。


     * 典型DP问题，自左至右，自底向上按部就班即可

Code

class Solution {
public:
    /* 
     * 典型DP问题，自左至右，自底向上按部就班即可
     *
     * */
    int minPathSum(vector<vector<int> > &grid) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(grid.size() == 0)    return 0;
        int rows = grid.size();
        int cols = grid[0].size();
        vector<int> tempRow(cols, 0);
        vector<vector<int> > tables(rows, tempRow);
        tables[0][0] = grid[0][0];
        for(int i = 1; i < rows; i++)
            tables[i][0] = grid[i][0] + tables[i-1][0];
        for(int i = 1; i < cols; i++)
            tables[0][i] = grid[0][i] + tables[0][i-1];
        for(int i = 1; i < rows; i++)
        {
            for(int j = 1; j < cols; j++)
            {
                tables[i][j] = grid[i][j] + std::min(tables[i-1][j], tables[i][j-1]);
            }
        } 
        return tables[rows-1][cols-1];
    }
};

pic