【线性DP】最大的正方形
2021/10/14 23:14:23
本文主要是介绍【线性DP】最大的正方形,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
【题目链接】
最大正方形
【题目描述】
在一个由 '0'
和 '1'
组成的二维矩阵内,找到只包含 '1'
的最大正方形,并返回其面积。
【输入输出样例】
输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出:4
【数据范围】
1 <= m, n <= 300
f[i][j] 取决于 f[i -1][j - 1],之后判断一下紫色区域是否都为1即可,如果为1,则加1。
1 const int N = 309; 2 int f[N][N]; 3 int res = 0; 4 class Solution { 5 public: 6 int maximalSquare(vector<vector<char>>& matrix) { 7 memset(f,0,sizeof f); 8 res = 0; 9 int n = matrix.size(),m = matrix[0].size(); 10 for(int i = 0;i < n;++i) 11 { 12 f[i][0] = matrix[i][0] - '0'; 13 res = max(res,f[i][0]); 14 } 15 for(int i = 0;i < m;++i) 16 { 17 f[0][i] = matrix[0][i] - '0'; 18 res = max(res,f[0][i]); 19 } 20 for(int i = 1;i < n;++i) 21 for(int j = 1;j < m;++j) 22 { 23 if(matrix[i][j] != '0') 24 { 25 for(int k = 0;k <= f[i - 1][j - 1];++k) //当前f[i][j]最大值受限于f[i - 1][j - 1] 26 { 27 int x = i - k,y = j - k; 28 if(x >= 0 && y >= 0 && matrix[i][y] == '1' && matrix[x][j] == '1') 29 f[i][j] += 1; 30 else break; 31 } 32 res = max(res,f[i][j]); 33 } 34 } 35 return res * res; 36 } 37 };
滚动数组优化:
1 const int N = 309; 2 int f[N]; 3 int res = 0; 4 class Solution { 5 public: 6 int maximalSquare(vector<vector<char>>& matrix) { 7 memset(f,0,sizeof f); 8 res = 0; 9 int n = matrix.size(),m = matrix[0].size(); 10 for(int i = 0;i < m;++i) 11 { 12 f[i] = matrix[0][i] - '0'; 13 res = max(res,matrix[0][i] - '0'); 14 } 15 for(int i = 0;i < n;++i) 16 res = max(res,matrix[i][0] - '0'); 17 for(int i = 1;i < n;++i) 18 { 19 20 for(int j = m - 1;j >= 1;--j) 21 { 22 f[j] = 0; 23 if(matrix[i][j] != '0') 24 { 25 for(int k = 0;k <= f[j - 1];++k) 26 { 27 int x = i - k,y = j - k; 28 if(x >= 0 && y >= 0 && matrix[i][y] == '1' && matrix[x][j] == '1') 29 f[j] += 1; 30 else break; 31 } 32 res = max(res,f[j]); 33 } 34 } 35 f[0] = matrix[i][0] - '0'; 36 } 37 38 return res * res; 39 } 40 };
DP做法:
1 const int N = 309; 2 int f[N][N]; 3 int res = 0; 4 class Solution { 5 public: 6 int maximalSquare(vector<vector<char>>& matrix) { 7 memset(f,0,sizeof f); 8 res = 0; 9 int n = matrix.size(),m = matrix[0].size(); 10 for(int i = 0;i < n ;++i) 11 { 12 f[i][0] = matrix[i][0] - '0'; 13 res = max(res,f[i][0]); 14 } 15 for(int i = 0;i < m;++i) 16 { 17 f[0][i] = matrix[0][i] - '0'; 18 res = max(res,f[0][i]); 19 } 20 for(int i = 1;i < n;++i) 21 for(int j = 1;j < m;++j) 22 if(matrix[i][j] == '0') 23 f[i][j] = 0; 24 else 25 { 26 f[i][j] = min(f[i][j - 1],min(f[i - 1][j - 1],f[i - 1][j])) + 1; 27 res = max(res,f[i][j]); 28 } 29 return res * res; 30 } 31 };
滚动数组优化的DP懒得写了,后面想起来再说吧...
这篇关于【线性DP】最大的正方形的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-30我的第一个Go命令行工具
- 2024-09-30初学者指南:轻松掌握模块化编程
- 2024-09-30顶级5款免费的IntelliJ插件,助你Java开发之路更顺畅
- 2024-09-30提高应用程序可用性:冗余和持久性
- 2024-09-30Twitter 系统设计面试示例
- 2024-09-30JSON对象入门教程:轻松掌握基础用法
- 2024-09-30封装入门:Java面向对象编程的第一步
- 2024-09-30后台交互入门:轻松掌握基础知识与实践技巧
- 2024-09-30轻松入门:后台交互教程详解
- 2024-09-30后台交互项目实战:新手指南