这是一道动态规划的题目,
第一时间想到的就是暴力搜索,但是暴力搜索的时间复杂度高达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) {
}
}