64最小路径和----动态规划

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) 
    {
        int r = grid.size(); //二维数组的行
        int c = grid[0].size();//二维数组的列
        //dp数组用来存放每个位置的最优解
        vector<vector<int>> dp(r, vector<int>(c, 0));//初始化dp二维数组的大小为r行c列
        //0,0位置的最优解等于该位置
        dp[0][0] = grid[0][0];
        //计算第i行的最优解
        for (int i = 1; i < c; i++)
        {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        //计算第j列的最优解
        for (int j = 1;j < r; j++)
        {
            dp[j][0] = dp[j - 1][0] + grid[j][0];
        }
        //计算第1行到第r-1行的最短路径和
        //第1列到第c-1列的最短路径和
        for (int i = 1; i < r; i++)
        {
            for (int j = 1; j < c; j++)
            {
                //位置i,j对应的最优解，应该选取左边和上面对应最优解的较小者加上当前对应grid数组中的值
                dp[i][j] = min(dp[i][j - 1],dp[i - 1][j])+grid[i][j];
            }
        }
        //返回最优解
        return dp[r - 1][c - 1];
    }
};

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

};

public int minPathSum(int[][] grid, int i, int j) {
    if (边界条件的判断) {
        return
    }

    //一些逻辑处理

    //取从上面走下来和从左边走过来的最小值+当前坐标的值
    return grid[i][j] + Math.min(minPathSum(grid, i - 1, j), minPathSum(grid, i, j - 1));
}

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) 
    {
        return FindMinPath(grid, grid.size() - 1, grid[0].size() - 1);
    }
    int FindMinPath(vector<vector<int>>& grid,int i,int j)
    {
        //到达起点，开始回溯计算
        if (i == 0 && j == 0)
        {
            return grid[i][j];
        }
        if (i == 0) //第一行只能从左边走过来
        {
            return grid[0][j] + FindMinPath(grid, i, j - 1);//前面一个点的值加上i不变，j-1
        }
        if (j == 0)//第一列只能从上面走下来
        {
            return grid[i][0] + FindMinPath(grid, i - 1, j);
        }
         //取从上面走下来和从左边走过来的最小值+当前坐标的值
        return grid[i][j] +min(FindMinPath(grid, i - 1, j),FindMinPath(grid,i,j-1));
    }
};

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) 
    {
        map<pair<int, int>, int> ret;
        return FindMinPath(grid, grid.size() - 1, grid[0].size() - 1,ret);
    }
    int FindMinPath(vector<vector<int>>& grid,int i,int j, map<pair<int, int>, int>& ret)
    {
        //如果当前位置的最短路径被计算过，那就直接返回
        if (ret.count({ i,j }) == 1)
            return ret[{i, j}];
        int res;//保存当前位置的最短路径和
        //到达起点，开始回溯计算
        if (i == 0 && j == 0)
        {
            res=grid[i][j];
        }
        //如果是第一行或者第一列，那么第一行或者第一列上的点的最短路径和就是当前点的值加上它前面一个点的值
        else if (i == 0)//第一行
        {
            res=grid[0][j] + FindMinPath(grid, i, j - 1,ret);//前面一个点的值加上i不变，j-1
        }
        else if (j == 0)//第一列
        {
            res=grid[i][0] + FindMinPath(grid, i - 1, j,ret);
        }
        else
        res=grid[i][j] +min(FindMinPath(grid, i - 1, j,ret),FindMinPath(grid,i,j-1,ret));
        //保存当前位置最短路径和和位置到ret容器
        ret[{i, j}] = res;
        return res;//返回当前位置最短路径和
    }
};