问题描述

给定一个二维数组 matrix ，Bob 必须从左上角出发，最后到达右下角，沿途只可以向下或者向右走。沿途的数字的累加就是距离累加和。返回最小距离累加和。

暴力递归

常规题型，不再赘述。

int process(const vector<vector<int>> &matrix, int x, int y)
{
    if(x < 0 || x >= matrix[0].size() || y < 0 || y >= matrix.size())
        return INT_MAX;
    if(x == matrix[0].size() - 1 && y == matrix.size() - 1)
        return matrix[y][x];//可别写成了[x][y]
    int down = process(matrix, x, y + 1);
    int right= process(matrix, x + 1, y);
    return matrix[y][x] + std::min(down, right);
}
int minPathSum(const vector<vector<int>> &matrix)
{
    return process(matrix, 0, 0);
}

动态规划

int help(const vector<vector<int>> &matrix, const vector<vector<int>> &dp, int x, int y)
{
    if(x < 0 || x >= matrix[0].size() || y < 0 || y >= matrix.size())
        return INT_MAX;
    if(x == matrix[0].size() - 1 && y == matrix.size() - 1)
        return matrix[y][x];
    return dp[y][x];
}
int minPathSum(const vector<vector<int>> &matrix)
{
    vector<vector<int>> dp(matrix[0].size(), vector<int>(matrix.size(), 0));
    for(int r = matrix.size() - 1; r >= 0; r--)
    {
        for(int c = matrix[0].size() - 1; c >= 0; c--)
        {
            int down = help(matrix, dp, c, r + 1);
            int right= help(matrix, dp, c + 1, r);
            dp[r][c] = matrix[r][c] + std::min(down, right);
        }
    }
    return dp[0][0];
}

空间压缩

滚动数组最常见的是空间压缩。本题的 dp 表中每个格子只依赖右边和下面的格子：

填表顺序为从下到上，从右到左。因为每个格子只依赖紧邻的右边和下边的格子，所以 dp 表可以压缩成单行，后续填表仅在这一行表格上滚动更新即可。其他说明参见代码：

int minPathSum(const vector<vector<int>> &matrix)
{
    int row = matrix.size() - 1;
    int col = matrix[0].size() - 1;
    vector<int> dp(matrix[0].size(), 0);
    
    //特例初始化
    dp[col] = matrix[row][col];//初始时刻dp为最后一行,且末尾格子为matrix[row][col];
    for(int c = col - 1; c >= 0; c--)
    {
        dp[c] = matrix[row][c] + dp[c+1];//初始化最后一行
    }
    for(int r = row - 1; r >= 0; r--)//从倒数第二行开始滚动打表
    {
        for(int c = col; c >= 0; c--)//从右往左打表
        {
            dp[c] = matrix[r][c] + std::min(dp[c], c == col ? INT_MAX : dp[c+1]);//注意边界条件
        }
    }
    return dp[0];
}

总结

• 空间压缩时最好不要使用统一处理法，而应该用特例初始化，先把初始条件加载好再进行数组的滚动。
• 没必要压缩空间，容易出错。