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

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

示例:

输入:
[
  [1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络Network所有。商业转载请联系官方授权,非商业转载请注明出处。
 
 
我的思路:
  1.动态规划(两种情况):
    1、横竖边缘的点(x=0||y=0)需要单独处理(只有向下或向右)直接叠加。
    2.非边缘的点(x!=0&&y!=0)需要单独处理(可以向下和向右),取左和上方向上最小的一方,再叠加当前点。
  2.递归
  3.广度优先
 
 
我的题解(动态规划):

class Solution {
public:
    int min(int a, int b)
    {
        return a < b ? a : b;
    }
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        int count = grid[0][0];
        for (int i = 1; i < m; i++)
        {
            count += grid[i][0];
            grid[i][0] = count;
        }

        count = grid[0][0];
        for (int k = 1; k < n; k++)
        {
            count += grid[0][k];
            grid[0][k] = count;
        }

        for (int i = 1; i<m; i++)
        {
            for (int k = 1; k < n; k++)
            {
                grid[i][k] = grid[i][k] + min(grid[i - 1][k], grid[i][k - 1]);
            }

        }

        return grid[m - 1][n - 1];
    }
};