矩阵的最小路径和（空间压缩）

╰半夏微凉° 2022-08-18 02:17 117阅读 0赞

题目：已知矩阵  
 1 3 5 9  
8 1 3 4  
5 0 6 1  
8 8 4 0

‰以1 ,3 ,1, 0 , 6,1 ,0路径和最小，所以返回12

下面代码示例给出通常动态规划解决方法空间复杂度为O(M\*N)，同时给出空间压缩之后的方法，空间复杂度为O(min\{M,N\})；

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <cstdio>
    #include <cmath>
    
    using namespace std;
    
    #define MATRIX_ROWS_LENGTHS 4
    #define MATRIX_COLS_LENGTHS 4
    
    /* 求出矩阵的最小路径和，该方法空间复杂度为O(M*N)
       dp[i][j]数组代表的意义为m[0][0]到m[i][j]的最小和*/
    int minMatrixPathSum1(int m[][MATRIX_COLS_LENGTHS])
    {
        if (m == NULL)
        {
            return 0;
        }
        int i = 0, j = 0;
        int dp[MATRIX_ROWS_LENGTHS][MATRIX_COLS_LENGTHS] = {0};
        dp[0][0] = m[0][0];
    
        /* 求出第一行的dp数值 */
        for(j = 1; j < MATRIX_COLS_LENGTHS; j++)
        {
            dp[0][j] = dp[0][j-1] + m[0][j];
        }
    
        /* 求出第一列的dp数值 */
        for(i = 0; i < MATRIX_ROWS_LENGTHS; i++)
        {
            dp[i][0] = dp[i-1][0] + m[i][0];
        }
    
        /* 求出剩下的dp数值 */
        for(i = 1; i < MATRIX_ROWS_LENGTHS; i++)
        {
            for(j = 1; j < MATRIX_COLS_LENGTHS; j++)
            {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + m[i][j];
            }
        }
    
        return dp[MATRIX_ROWS_LENGTHS-1][MATRIX_COLS_LENGTHS-1];
    }
    
    /* 经过空间压缩之后，空间复杂度可以变为O(min{M,N}) */
    int minMatrixPathSum2(int m[][MATRIX_COLS_LENGTHS])
    {
        if (m == NULL)
        {
            return 0;
        }
        int i = 0, j = 0;
    
        int moreLen = max(MATRIX_ROWS_LENGTHS,MATRIX_COLS_LENGTHS);//行数与列数较大的数
        int lessLen = min(MATRIX_ROWS_LENGTHS,MATRIX_COLS_LENGTHS);//行数与列数较小的数
        bool rowmore = (moreLen == MATRIX_ROWS_LENGTHS);  //行数是不是大于等于列数
        int minPath = 0;
    
        int* arr = new int[lessLen]; //辅助数组的长度仅仅为行数与列数的最小值
        arr[0] = m[0][0];
    
        /* 求出第一行的dp数值 */
        for(i = 1; i < lessLen; i++)
        {
            arr[i] = arr[i-1] + (rowmore ? m[0][i] : m[i][0]);
        }
    
        /* 求出剩下的dp数值 */
        for(i = 1; i < moreLen; i++)
        {
            arr[0] = arr[0] + (rowmore ? m[i][0] : m[0][i]);
            for(j = 1; j < lessLen; j++)
            {
                arr[j] = min(arr[j-1],arr[j]) + (rowmore ? m[i][j] : m[j][i]);
            }
        }
    
        minPath = arr[lessLen-1];
        delete[] arr;
    
        return minPath;
    }
    int main()
    {
       int matrix[MATRIX_ROWS_LENGTHS][MATRIX_COLS_LENGTHS] =
       {
       {1,4,9,18},
        {9,5,8,12,},
        {14,5,11,12},
        {22,13,15,12}
       };
    
        cout << minMatrixPathSum1(matrix) << endl;
        cout << minMatrixPathSum2(matrix) << endl;
    }

本题中的压缩空间的方法几乎可以应用到所有的二维动态规划的题目，通过一个数组滚动更新的方式无疑节省了大量的空间。没有优化之前，去的某个位置动态规划值的过程是在矩阵中进行两次寻址，程序的常数时间也得到了一定程度的加速，但是空间压缩的方法是有局限性的，如果本题改成打印具有最小路径和的路径，就不能使用空间压缩的方法。