关于leetcode221如何用递归+记忆化搜索方式求解的疑惑，请老师帮忙指点一下

Question

老师好，看了老师的教程，对于动态规划类问题，我都想尝试用递归方式先做一下，关于leetcode221号题目，用递归方式有点没想通，想请老师指点一下：
下面是主函数，主要是镜像一个数组递归使用，然后调用dfs进行递归，从最右下角的位置开始向坐上递归

int maximalSquare(char** matrix, int matrixSize, int* matrixColSize){
int i,j,res;
int **mirror;
if(matrixSize == 0)
return 0;

//镜像一个数组
mirror = malloc(sizeof(int *) * matrixSize);
for(i = 0; i < matrixSize; ++i){
mirror[i] = malloc(sizeof(int) * matrixColSize[0]);
memset(mirror[i],0,sizeof(int) * matrixColSize[0]);
}

res = dfs(mirror, matrixSize - 1, matrixColSize[0] - 1, matrixSize, matrixColSize[0]);
return res * res;
}

下面是递归的函数（dfs），我的思路是：
1.先不取当前的点，只取(x,y-1) (x-1,y)(x-1,y-1)三个点继续递归，三者取最大的
2.如果当前点是1，再取当前点，判断当前点和其他三个点都是1，则满足正方形，1+dfs继续递归三个点取最小的，然后再和第一点的结果取最大的
实际测试这个写法是有问题的，比如下面这个测试例：
[[“1”,“1”,“0”],[“1”,“1”,“1”]]，感觉问题的关键在下面者一行的else分之里：
else
res = 1; //这个else分之的处理感觉有问题
//res = myMax(1, res);
但是没想出来如何修正，或者我的这个递归逻辑根本不对，还请老师指点一下，感谢
然后我又改了一下，把res =1 换成 res = myMax(res, 1)，这样另外一种场景又过不了：[[“0”,“0”,“0”,“1”],[“1”,“1”,“0”,“1”],[“1”,“1”,“1”,“1”],[“0”,“1”,“1”,“1”],[“0”,“1”,“1”,“1”]]，相当于一个大正方形连着一个小正方形，这块处理感觉把自己绕晕了，还望bobo老师指点一下

int dfs(int ** matrix, int x, int y, int m, int n){
int res = 0;
if(!isArea(x, y, m, n))
return 0;

//不取当前结点
res = myMax(res, dfs(matrix, x, y - 1, m, n));
res = myMax(res, dfs(matrix, x - 1, y, m, n));
res = myMax(res, dfs(matrix, x - 1, y - 1, m, n));

//取当前结点
if(matrix[x][y] == 1){
if(isArea(x, y - 1, m, n) && matrix[x][y - 1] == 1 &&
isArea(x - 1, y, m, n) && matrix[x - 1][y] == 1 &&
isArea(x - 1, y - 1, m, n) && matrix[x - 1][y - 1] == 1){
res = myMax(res, my_min(my_min(dfs(matrix, x, y - 1, m, n), dfs(matrix, x - 1, y, m, n)), dfs(matrix, x - 1, y - 1, m, n)) + 1);
}
else
res = 1; //这个else分之的处理感觉有问题
//res = myMax(1, res);
}

return res;
}

Answer 1

liuyubobobo 2020-01-07 08:14:08

我写了一版记忆化搜索，看看你能不能理解？和你的思路比对一下，看一下问题在哪里？

https://github.com/liuyubobobo/Play-Leetcode/blob/master/0221-Maximal-Square/cpp-0221/main5.cpp

继续加油！：）

• 提问者 慕哥8233928 #1

  非常感谢！

• 提问者 慕哥8233928 #2

  谢谢bobo老师! 看了老师的思路，发现自己的思路是试图利用最右下角的坐标只通过递归向左上角扩散，这样判断正方形出了问题；换成老师的思路，其实用二维循环遍历每个坐标进行递归判断正方形非常方便省事，加上记忆化时间复杂度也在O(n^2)

• liuyubobobo 回复 提问者 慕哥8233928 #3

  每一次 dfs，求解以某个点为右下角的最大正方形的边长。我们需要看所有的正方形，也就是每一个点都有可能是结果正方向的右下角，所以要遍历一遍。关键在于递归函数 dfs 的语义是什么。继续加油！：）