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

来源:1-1 算法面试不仅仅是正确的回答问题

慕哥8233928

2020-01-04

老师好,看了老师的教程,对于动态规划类问题,我都想尝试用递归方式先做一下,关于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;
}

写回答

1回答

liuyubobobo

2020-01-07

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


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


继续加油!:)

1
3
liuyubobobo
回复
慕哥8233928
每一次 dfs,求解以某个点为右下角的最大正方形的边长。我们需要看所有的正方形,也就是每一个点都有可能是结果正方向的右下角,所以要遍历一遍。关键在于递归函数 dfs 的语义是什么。继续加油!:)
2020-01-12
共3条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7410 学习 · 1150 问题

查看课程