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

图解动态规划算法思想

此时可以求得最小路径和为7,

通过上面例子我们可以得出：要求的（i,j)位置的最优解，我们只需要比较该位置上方（i,j-1)和左方（i-1,j)的最优解，取最小值再加上(i,j)当前位置对应的grid数组的值即可，这样我们就得到了递归公式

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];
    }
};

• 我们看到二维数组dp和二维数组grid的长和宽都是一样的，没必要再申请一个dp数组，完全可以使用grid，来看下代码

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];
    }

};

递归解法：

• 我们还可以把上面的动态规划改为递归，定义一个函数

• minPathSum(int[][] grid, int i, int j)表示从左上角到坐标(i，j)的最短路径和，那么同样道理，要走到坐标(i，j)只能从上面下来或者左边过来。所以代码轮廓我们大致能写出来

• 如果这里递归采用反向计算，那么是在回溯过程中计算重目标点到达起点的最小路径和，也被称为自下而上的递归

• 如果是在从起点不断往终点探索过程中计算出结果，那么称为自上而下的递归

• 这里我们从终点开始，通过不断递归到达起点，在回溯过程中计算从起点到终点的距离

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));
    }
};

• 因为这里面的递归会导致大量的重复计算，所以还是老方法，就是把计算过的值存储到一个map中，下次计算的时候先看map中是否有，如果有就直接从map中取，如果没有再计算，计算之后再把结果放到map中，可以理解为记忆化递归，来看下代码

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;//返回当前位置最短路径和
    }
};