关于滚动数组

﹏ヽ暗。殇╰゛Y 2022-07-15 11:16 143阅读 0赞

# Minimum Path Sum #

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

## 普通的DP解决方案 ##

> DP的4个基本要素：  
> 状态（State）  
> 递推方程（Function）  
> 初始化（Initialization）  
> 结果（Answer）

1.  State：f\[x\]\[y\]从坐标(0,0)到(x,y)的最短路径
2.  Function：f\[x\]\[y\] = min\{ f\[x-1\]\[y\], f\[x\]\[y-1\] \} + (x, y)
3.  Initialization: f\[0\]\[0\] = A\[0\]\[0\], f\[i\]\[0\] = sum\{ (0,0) -> (i, 0) \}, f\[0\]\[i\] = sum\{ (0, 0) -> (0, i) \}
4.  Answer: f\[m-1\]\[n-1\]

int minPathSum(vector<vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
    
        int m = grid.size();
        int n = grid[0].size();
    
        vector<vector<int>> ret(m, vector<int>(n, 0));
    
        ret[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            ret[i][0] = grid[i][0] + ret[i-1][0];
        }
    
        for (int i = 1; i < n; i++) {
            ret[0][i] = grid[0][i] + ret[0][i-1];
        }
    
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                ret[i][j] = min(ret[i-1][j], ret[i][j-1]) + grid[i][j];
            }
        }
    
        return ret[m-1][n-1];
    }

## 滚动数组优化空间复杂度 ##

上面正常的求解时的空间复杂度为O(m\*n)，那么可以使用滚动数组优化空间复杂度为O(m) 或O(n)。  
使用滚动数组优化空间复杂度有两种方式：

1.  对行遍历进行优化
2.  对列遍历进行优化

通常习惯先按行遍历再按列遍历，有状态转移方程 f\[x\]\[y\] = (x, y) + min\{ f\[x-1\]\[y\], f\[x\]\[y-1\] \} 知，**想要优化行遍历，那么f\[y\]保存的值应为第x行第y列的值（此时，f\[y\] = f\[x\]\[y\]），在求第x+1行第y列时，会用到之前保存的f\[y\]和已经求得的f\[y-1\]的值。类似于行扫描，先求得上一行每一列的结果，并且在下一行求解每一列时用到上一行每一列的结果。因此只需要列数空间就可以完成优化。**由于无行下标信息，故初始化时仅能对第一个元素初始化，分析时可以画图理解。

// 对行遍历进行优化
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
    
        int m = grid.size();
        int n = grid[0].size();
    
        // 滚动数组    
        vector<int> ret(n, INT_MAX); // 因求min，初始化为INT_MAX
        ret[0] = 0;
    
        for (int i = 0; i < m; i++) {
            // 初始化第i行第0列
            ret[0] = ret[0] + grid[i][0];
    
            // ret[j]保存第i行第j列的结果
            for (int j = 1; j < n; j++) {
                // min(ret[j], ret[j-1])中保存的都是i-1行的第j列，j-1列的结果
                ret[j] = min(ret[j], ret[j-1]) + grid[i][j];
            }
        } 
    
        return ret[n-1];

// 对列遍历优化
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
    
        int m = grid.size();
        int n = grid[0].size();
    
        vector<int> ret(m, INT_MAX);
        ret[0] = 0;
    
        for (int j = 0; j < n; j++) {
            ret[0] = ret[0] + grid[0][j];
            for (int i = 1; i < m; i++) {
                ret[i] = min(ret[i], ret[i-1]) + grid[i][j];
            }
        } 
    
        return ret[m-1];

# 参考题目 #

[62. Unique Paths][]  
[62. Unique Paths解析][62. Unique Paths 1]

[62. Unique Paths]: https://leetcode.com/problems/unique-paths/
[62. Unique Paths 1]: https://discuss.leetcode.com/topic/15265/0ms-5-lines-dp-solution-in-c-with-explanations