LeetCode 64.最小路径和

LeetCode 64.最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步

思路：
f[i,j]表示，从[0,0]走到[i,j]的路径和，属性为Min。

代码：

class Solution {
public:
    vector<vector<int>> f;
    int minPathSum(vector<vector<int>>& grid) {
        //还是dp
        int n=grid.size();
        int m=grid[0].size();
        f = vector<vector<int>>(n,vector<int> (m,1100)); 

        f[0][0]=grid[0][0];

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(i) f[i][j]=min(f[i][j],f[i-1][j] + grid[i][j]);
                if(j) f[i][j]=min(f[i][j],f[i][j-1] + grid[i][j]);
            }
        }
        return f[n-1][m-1];
    }
};