力扣(LeetCode)1684. 统计一致字符串的数目(C++)

动态规划

计算每个格子，上下左右，包含 $1$ 的数目。$min(dp[i][j][left],dp[i][j][right],dp[i][j][up],dp[i][j][down])$ 即每个格子的加号阶数。
问题转化为 $dp$ 问题。 考虑到，取的是上下左右的最小值，我们可以在遍历时用 $dp[i][j]$ 保存最小值，就可以将第三个状态省略了。

参考链接 ： ylb[Python3/Java/C++/Go] 一题一解：动态规划

代码展示

class Solution {
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        vector<vector<int>> dp(n,vector<int>(n,n));//dp是n行的vector,每行n个vector,初始化每个数n
        for(auto x:mines) dp[x[0]][x[1]] = 0;//mines中所有坐标，对应dp置为0
        for(int i =0;i<n;i++){
            int left=0,right=0,up=0,down=0;
            for(int j=0,k=n-1;j<n;j++,k--){//由矩阵的对称性。
                left = dp[i][j]?left+1:0;
                right = dp[i][k]?right+1:0;
                up = dp[j][i]?up+1:0;
                down = dp[k][i]?down+1:0;
                dp[i][j] = min(dp[i][j],left);
                dp[i][k] = min(dp[i][k],right);
                dp[j][i] = min(dp[j][i],up);
                dp[k][i] = min(dp[k][i],down);
            }
        }
        int ans =0;
        for(auto x:dp)
            for(auto y:x)
                ans = max(ans,y);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

1. 时间复杂度: $O(n^2)$， 填充 $dp$ 矩阵和求 $ans$ 时，都遍历了一次 $dp$ 。时间复杂度 $O(n^2)$ 。
2. 空间复杂度: $O(n^2)$。 $dp$ 矩阵的空间复杂度 $O(n^2)$ 。