题意

给一个$n\cdot mn\backslash cdot\; m$n⋅m的二维数组，从左上向右下走，只能$i+=1i+=1$i+=1或$j+=1j+=1$j+=1或同时$i+=1,j+=1i+=1,j+=1$i+=1,j+=1 求经过的块的值的和的最小值。

其中 $nn$n和$mm$m 最大取到$300300$300

每个块是非负值，最大取到$100100$100

解法

深度搜索(TLE)

设计深度搜索状态 $dfs(i,j)=dfs(i,j)\; =$dfs(i,j)=从$i,ji,j$i,j开始走的最小总和

那么有 $dfs(i,j)=presentVolumn\left[i\right]\left[j\right]+min\left(dfs\right(i+1,j),dfs(i,j+1),dfs(i+1,j+1\left)\right)dfs(i,j)\; =\; presentVolumn[i][j]\; +\; min(dfs(i+1,j),dfs(i,j+1),dfs(i+1,j+1))$dfs(i,j)=presentVolumn[i][j]+min(dfs(i+1,j),dfs(i,j+1),dfs(i+1,j+1))

控制一下边界$dfs(1,1)dfs(1,1)$dfs(1,1) 即是要求的答案，转换成代码

代码

class Solution:
    
    def dfs(self,presentVolumn,i,j): # 当前位置在i,j
        if i+1 == len(presentVolumn) and j+1 == len(presentVolumn[0]):
            return presentVolumn[i][j]
        return presentVolumn[i][j] + min([
            0x3f3f3f3f if i+1 >= len(presentVolumn)    else self.dfs(presentVolumn, i+1, j), # 向下
            0x3f3f3f3f if j+1 >= len(presentVolumn[0]) else self.dfs(presentVolumn, i, j+1), # 向右
            0x3f3f3f3f if i+1 >= len(presentVolumn) or j+1 >= len(presentVolumn[0]) else self.dfs(presentVolumn, i+1, j+1) # 向对角线方向
        ])
        
    def selectPresent(self , presentVolumn ):
        return self.dfs(presentVolumn,0,0)

复杂度分析

空间复杂度: 搜索的核心为dfs，其栈的使用与搜索深度有关，因此空间复杂度为$O(m+n)O(m+n)$O(m+n)

时间复杂度: 搜索本质相当于尝试了所有方案一次,在每一个位置，最坏情况有3种走法， 最大的路径长度为$m+n-2m+n-2$m+n−2,时间复杂度为$O\left(3^{n+m-2}\right)O(3^\{n+m-2\})$O(3n+m−2), 对于题目的范围稍大肯定会超时

动态规划

注意到如果一个点，的左边，左上，上方的的最小值确定了，那么它的最小值也是确定。

$当前位置最小值=当前位置的值+min\left(左边最小值，左上最小值，上方最小值\right)当前位置最小值\; =\; 当前位置的值\; +\; min(左边最小值，左上最小值，上方最小值)$当前位置最小值=当前位置的值+min(左边最小值，左上最小值，上方最小值)

所以除了原始提供的二维数组，我们建立一个最小值数组，记录每个位置能达到的最小值。

以题目原始数组[[1,2,3],[2,3,4]]为例，初始化最小值数组，边界以外的地方和为INF=0x3f3f3f3f

依次处理每个单元格：

处理(1,2)

处理(1,3)

处理(2,1)

处理(2,2)

处理(2,3)

所以最小和为7。

把上述步骤变成代码，有：

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param presentVolumn int整型vector<vector<>> N*M的矩阵，每个元素是这个地板砖上的礼物体积
     * @return int整型
     */
    int selectPresent(vector<vector<int> >& presentVolumn) {
        vector<vector<int> > m(presentVolumn.size(),vector<int>(presentVolumn[0].size(),0)); // 每个位置最小值的二维数组
        m[0][0] = presentVolumn[0][0];
        for(int i = 0;i<presentVolumn.size();i++){
            for(int j = 0;j<presentVolumn[0].size();j++){
                if(i == 0 && j == 0)continue;
                int lvalue = i>0?m[i-1][j]:0x3f3f3f3f; // 左边最小值
                int tvalue = j>0?m[i][j-1]:0x3f3f3f3f; // 上面最小值
                int ltvalue = i>0&&j>0?m[i-1][j-1]:0x3f3f3f3f; // 左上最小值
                m[i][j] = presentVolumn[i][j] + min(lvalue, min(tvalue, ltvalue));
            }
        }
        return m[m.size()-1][m[0].size()-1];
    }
};

复杂度分析

空间复杂度: 我们按照原始数组的大小对应建立一个最小值数组。所以空间复杂度为$O\left(mn\right)O(mn)$O(mn)

时间复杂度: 我们对最小值数组每个位置遍历，对于一个具体的位置，它的取值来源与常数个块的值，因此时间复杂度为$O\left(mn\right)O(mn)$O(mn)