LeetCode 64 最小路径和

1. 题目描述

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

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

2. 题解

动态规划

3. 代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        if (!m) return 0;
        int n=grid[0].size();
        if (!n) return 0;
        vector<int> f(n);
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if (j==0) f[j]=f[j];
                else if (i==0) f[j]=f[j-1];
                else f[j]=min(f[j],f[j-1]);
                f[j]+=grid[i][j];
            }
        }
        return f[n-1];
    }
};