矩阵的最小路径和（动态规划）

题意

给定一个二维数字数组,求从左上角,走到右下角,路径上值的最小和

思路分析

相邻关系

如果走到最后路径和最小,那么它上一步来源是上方或者左方

int f(i,j){
    return min(f(i-1,j),f(i,j-1)) + matrix[i][j];
}

递归转递推

对于任意一个位置,走到它的最小值是唯一的

把上面的递归式子反向改为递推

for(int i = 0;i<matrix.size();i++){
    for(int j = 0;j<matrix[0].size();j++){
		dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + matrix[i][j];
    }
}

空间优化

注意到每个值,仅与它上方和左方的值推得,所以对于上述的遍历方式,只需要存储上一排的值,可以循环利用空间

for(int i = 0;i<matrix.size();i++){
    for(int j = 0;j<matrix[0].size();j++){
		dp[j] = min(dp[j],dp[j-1]) + matrix[i][j];
    }
}

边界处理

这里主要的边界两处,初始值的一排的上一排值,和每排的最左侧的上一个值.

这里通过设置为无限大INF来进行运算

而对于初始坐标,设置为0

// 第一排
vector<int> ans(m,INF);
ans[0] = 0;

// 第一列
j==0?INF:ans[j-1]

样例数据为例

以样例数据1为例,新建的计算最小值的表,在压缩前的值如图所示

题解

所以整合上面的内容

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        const int INF = 0x3f3f3f3f;
        int n = matrix.size();
        int m = matrix[0].size();
        vector<int> ans(m,INF);
        ans[0] = 0;
        for(int i = 0;i<n;i++){ // 每行
            for(int j = 0;j<m;j++){ // 每列
                ans[j] = min(ans[j], j==0?INF:ans[j-1]) + matrix[i][j]; // 取最小值
            }
        }
        return ans[m-1];
    }
};

复杂度分析

空间复杂度: 存储状态数组大小是行的长度,所以空间复杂度为$O(n)O(n)$

时间复杂度: 状态转移代价是常数代价,所以时间复杂度为$O(nm)O(nm)$