每日leetcode第0037天 0221. Maximal Square

这是一道动态规划的题目,

第一时间想到的就是暴力搜索,但是暴力搜索的时间复杂度高达4次方。

所以我们就创建一个table来记录这个点左上方最大的正方形的边长。

在计算状态转移方程式的时候,我们要考虑当前点是1还是0,如果是0则为0,为1的话就需要将左上、上、左三个点取出最小值后加一。

初始化initialization:
for (int i = 0; i < m; ++i) side[i][0] = matrix[i][0];
for (int i = 0; i < n; ++i) side[0][i] = matrix[0][i];

状态转移方程式optimum-value function:
side[i][j] = matrix[i][j] ? min(min(side[i-1][j-1], side[i-1][j]), side[i][j-1]) + 1 : 0;

循环公式recurrent formula:
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
}
}

 



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。