二维矩阵从左上角到右下角路径的最小和

问题：LeetCode第64题-求解最小路径和

给定一个二维数组m行，n列。假设这个二维数组中每个单元格的值都是正整数，表示从该单元格经过时需要花费的成本。
那么求从左上角第一个单元格到右下角最后一个单元格的路径中，花费的最小成本是多少？
约束条件为：每次只能向下或者向右移动一步。

说明：

给定一个m=3，n=3的二维数组cost，如下图所示，从左上角的第一个单元格出发，可以向右，向下走，最终达到右下角。因为路径 1→3→1→1→1 的总和最小,所以输出的结果为7

图例.png

题解

暴力递归算法
记忆化搜索算法
二维动态规划算法
一维动态规划算法

1. 暴力递归

利用递归，对于每个元素我们考虑两条路径，向右走和向下走，在这两条路径中挑选路径权值和较小的一个。递推公式如下：
cost(i,j) = grid[i][j] + min(cost(i+1,j),cost(i,j+1))

实现代码如下：

/**
 @name 暴力递归法
 @brief
   递归公式:
  cost(i,j) = grid[i][j] + min(cost(i+1,j),cost(i,j+1))
 以当前点为原点,依次向右和向下计算代价值
 */
int calculate(vector<vector<int>> &grid,int i,int j) {
    size_t bound_m = grid.size();  //行
    size_t bound_n = grid[0].size(); //列
    if (i == bound_m || j == bound_n) return INT_MAX;  //右边界，下边界
    if (i == (bound_m -1) && j == (bound_n -1)) return grid[i][j];   //到目的地右下角直接返回
    return grid[i][j] + min(calculate(grid, i+1, j), calculate(grid, i, j+1));  //递归查找最短路径
}

int DPAlgorithm::minPathSum(vector<vector<int>> &grid) {
    //从0,0点开始出发
    return calculate(grid, 0, 0);
}

复杂度以及优化的点

复杂度
时间复杂度：O(2 ^m+n)。每次移动最多可以有两种选择。
空间复杂度：O(m+n))。递归的深度是 m+n
优化的点
当我们从左上角(0,0)开始出发的时候，因为只能沿着右和下2个方向，所以走1->3 或者1->1,这样依次走下去，必然会经过2次5，例如：1->3->5...以及1->1>5...，可以想到，当走的5的时候，5的走法也只有右和下2种走法，所以这样就会造成从这个点出发到右下角(2,2)被计算了2次，如果这个矩阵很大的话，那么这样的点就会有很多，就会被重复很多次，时间复杂度不言而喻。如何优化？

LeetCode提交结果：

暴力递归提交结果.png

2. 记忆化搜索算法

在暴力递归的基础上进行优化，目的是将每次递归计算后的结果保存起来，下次递归计算的时候先去查表，检查是否有保存过的计算结果，如果有直接返回，如果没有计算后更新表。

实现代码如下：

//申请一张二维表
static vector<vector<int>> table;

int calculate2(vector<vector<int>> &grid,int i,int j) {
    size_t bound_m = grid.size();  //行
    size_t bound_n = grid[0].size(); //列
    //判断边界
    if (i == bound_m || j == bound_n) return INT_MAX;
    //到达目的地，直接返回
    if (i == (bound_m -1) && j == (bound_n -1)) return grid[i][j];
    //查表，不为空直接返回结果
    if (table[i][j] != -1) return table[i][j];
    //结果求和并存表
    int sum = grid[i][j] + min(calculate2(grid, i+1, j), calculate2(grid, i, j+1));
    table[i][j] = sum;
    return sum;
}

int DPAlgorithm::minPathSum(vector<vector<int>> &grid) {
    //从0,0点开始出发
    //暴力递归
//    return calculate(grid, 0, 0);
//    记忆搜索算法
    size_t m = grid.size();  //行
    size_t n = grid[0].size(); //列
    //初始化m*n表的大小以及内容
    table = vector<vector<int> >(m,vector<int> (n,-1));
    return calculate2(grid, 0, 0);
    
}

复杂度以及优化的点

复杂度
时间复杂度：O(mn)。
空间复杂度：O(mn)。
优化的点
通过使用记忆搜索算法进行优化，时间复杂度已经被显著的降低了，但空间复杂度却显著的增加了，为了进一步降低算法的复杂度，我们继续进行优化。

LeetCode提交结果：

记忆化搜索提交结果.png

3. 二维动态规划算法

新建一个额外的dp矩阵，与原矩阵大小相同。在这个矩阵中，dp(i,j)表示从左上角到[i,j]的最小路径和。我们根据左上角的值，很容易初始化出第一行和第一列中 dp值对应的原矩阵的值。然后根据初始化的值，去更新整个dp矩阵的值，对于每个元素[i,j]考虑其由左边和上边的值计算得出，因此获得最小路径有如下递推公式：
dp(i,j)=grid(i,j) + min(dp(i-1,j),dp(i,j-1))

dp矩阵更新过程如下图：

dp矩阵更新过程.png

从上图可以看到，当我们初始化dp矩阵之后，剩下的操作根据递推公式依次填充每一行和每一列，dp右下角便是我们要求的结果。

实现代码如下：

int DPAlgorithm::minPathSum(vector<vector<int>> &grid) {
    //从0,0点开始出发
    //暴力递归
//    return calculate(grid, 0, 0);
//    记忆搜索算法
//    size_t m = grid.size();  //行
//    size_t n = grid[0].size(); //列
//    //申请一张m*n的表
//    table = vector<vector<int> >(m,vector<int> (n,-1));
//    return calculate2(grid, 0, 0);
    //二维dp算法
    size_t m = grid.size();  //行
    size_t n = grid[0].size(); //列
    vector<vector<int>> dp(m,vector<int>(n,-1));
    dp[0][0] = grid[0][0];
    //更新第一行
    for (int i = 1; i < n; i++) {
        dp[0][i] = grid[0][i] + dp[0][i-1];
    }
    //更新第一列
    for (int i = 1; i < m; i++) {
        dp[i][0] = grid[i][0] + dp[i-1][0];
    }
    //根据递推公式,按行更新dp表
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[m-1][n-1];
}

复杂度以及优化的点

复杂度
时间复杂度：O(mn)，遍历整个矩阵恰好一次。
空间复杂度：O(mn)，额外的一个同大小矩阵。
优化的点
通过使用二维动态规划算法，虽然可以解决这个问题，但看起来时间复杂度以及空间复杂度和记忆搜索算法基本一样，那是否有方法继续优化呢？

LeetCode提交结果：

二维dp算法提交结果.png

4. 一维动态规划算法

通过分析二维动态规划算法，发现当更新完第一行和第一列以后，每次都是一行一行的对dp矩阵的其他位置进行更新，那么可不可以只用一个数组就完成对其他位置的更新呢？答案是可以的！可以将一维数组理解为从上往下滚动的数组。因为我们并不关心中间的状态是什么，只需要将这个数组滚动到最后，计算最后的结果值即可。本题分析如下图所示：

一维动态规划.png

从图中可以看到，一共滚动了三次，第一次滚动初始化dp数组，接下来每次借助二维数组和dp数组中的值对数组进行滚动更新，直到更新到最后一行（也就是本题的第三行），最后一个标红的位置就是我们所求的结果。

实现代码如下：

int DPAlgorithm::minPathSum(vector<vector<int>> &grid) {
    //一维dp算法
    size_t m = grid.size();  //行
    size_t n = grid[0].size(); //列
    vector<int> dp(n,-1);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            
            if (i == 0 && j == 0) {
                //更新第一个元素
                dp[j] = grid[i][j];
            } else if (i == 0 && j > 0) {
                //更新第一行
                dp[j] = grid[i][j] + dp[j-1];
            } else if (j == 0 && i > 0) {
                //更新第一列
                dp[j] = grid[i][j] + dp[j];
            } else {
                //更新其他位置
                dp[j] = grid[i][j] + min(dp[j-1], dp[j]);
            }
        }
    }
    return dp[n-1];
}

复杂度以及优化的点

复杂度
时间复杂度：O(mn),遍历整个矩阵恰好一次。
空间复杂度：O(n)，额外的一维数组，和一行大小相同

还能继续优化吗？

答案是可以的，可以将一维dp算法的思路应用到二维dp算法上面。什么意思？因为我们在计算的过程中并不关心中间状态，而只关系最后一行，所以，我们可以免去申请二维dp矩阵，直接在给定的矩阵上进行滚动，这样，空间复杂度可以降为O(1)。但这样会改变原矩阵中的值，需要根据实际情况来使用，本题是可以使用的。