关于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;
}
2回答
-
liuyubobobo
2020-01-07
00 -
慕哥8233928
提问者
2020-01-04
又改了一下,把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老师指点一下
00
相似问题