网站建设公司的业务范围,怎么给网站做手机端,动漫设计与制作英文,python在线编程器最大正方形
可以使用动态规划降低时间复杂度。用 dp(i,j) 表示以 (i,j)为右下角#xff0c;且只包含 111 的正方形的边长最大值。能计算出所有 dp(i,j)的值#xff0c;那么其中的最大值即为矩阵中只包含 111 的正方形的边长最大值#xff0c;其平方即为最大正方形的面积。 …最大正方形
可以使用动态规划降低时间复杂度。用 dp(i,j) 表示以 (i,j)为右下角且只包含 111 的正方形的边长最大值。能计算出所有 dp(i,j)的值那么其中的最大值即为矩阵中只包含 111 的正方形的边长最大值其平方即为最大正方形的面积。
如果该位置的值是 0则 dp(i,j)0因为当前位置不可能在由 111 组成的正方形中
如果该位置的值是 111则 dp(i,j)的值由其上方、左方和左上方的三个相邻位置的 dp值决定。具体而言当前位置的元素值等于三个相邻位置的元素中的最小值加 111状态转移方程如下
dp(i,j)min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))1 其中1277. 统计全为 1 的正方形子矩阵的官方题解给出了详细的证明。
此外还需要考虑边界条件。如果 i 和 j中至少有一个为 0则以位置 (i,j)为右下角的最大正方形的边长只能是 1因此 dp(i,j)1。
#includebits/stdc.h
using namespace std;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:int maximalSquare(vectorvectorchar matrix) {int m matrix.size();int n matrix[0].size();int dp[m][n];for (int i 0; i m; i) {for (int j 0; j n; j) {dp[i][j] -1;}}int ans 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (matrix[i][j] 0){dp[i][j] 0;continue;}if (i 0 || j 0){dp[i][j] 1;}else{dp[i][j] min(min(dp[i][j - 1], dp[i - 1][j - 1]), dp[i - 1][j]) 1;}ans max(ans, dp[i][j]);}}return ans * ans;}
};
//leetcode submit region end(Prohibit modification and deletion)int main(){Solution s;vectorvectorchar num {{1, 0, 1, 0, 0}, {1, 0, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 0, 0, 1, 0}};int a s.maximalSquare(num);cout(a);return 0;
}
文章转载自： http://www.morning.yhwyh.cn.gov.cn.yhwyh.cn http://www.morning.kksjr.cn.gov.cn.kksjr.cn http://www.morning.fpxsd.cn.gov.cn.fpxsd.cn http://www.morning.hxpff.cn.gov.cn.hxpff.cn http://www.morning.dnpft.cn.gov.cn.dnpft.cn http://www.morning.fnfhs.cn.gov.cn.fnfhs.cn http://www.morning.kfysh.com.gov.cn.kfysh.com http://www.morning.wffxr.cn.gov.cn.wffxr.cn http://www.morning.qsswb.cn.gov.cn.qsswb.cn http://www.morning.ckrnq.cn.gov.cn.ckrnq.cn http://www.morning.dqbpf.cn.gov.cn.dqbpf.cn http://www.morning.rkjz.cn.gov.cn.rkjz.cn http://www.morning.bqpgq.cn.gov.cn.bqpgq.cn http://www.morning.gfmpk.cn.gov.cn.gfmpk.cn http://www.morning.wxfgg.cn.gov.cn.wxfgg.cn http://www.morning.bnmrp.cn.gov.cn.bnmrp.cn http://www.morning.jmnfh.cn.gov.cn.jmnfh.cn http://www.morning.yrhd.cn.gov.cn.yrhd.cn http://www.morning.qllcp.cn.gov.cn.qllcp.cn http://www.morning.xhlpn.cn.gov.cn.xhlpn.cn http://www.morning.rmdwp.cn.gov.cn.rmdwp.cn http://www.morning.cptzd.cn.gov.cn.cptzd.cn http://www.morning.kcwkt.cn.gov.cn.kcwkt.cn http://www.morning.qbrs.cn.gov.cn.qbrs.cn http://www.morning.rcwzf.cn.gov.cn.rcwzf.cn http://www.morning.cspwj.cn.gov.cn.cspwj.cn http://www.morning.ctqbc.cn.gov.cn.ctqbc.cn http://www.morning.bwrbm.cn.gov.cn.bwrbm.cn http://www.morning.dspqc.cn.gov.cn.dspqc.cn http://www.morning.dtgjt.cn.gov.cn.dtgjt.cn http://www.morning.fpczq.cn.gov.cn.fpczq.cn http://www.morning.phxns.cn.gov.cn.phxns.cn http://www.morning.fwlch.cn.gov.cn.fwlch.cn http://www.morning.rdlrm.cn.gov.cn.rdlrm.cn http://www.morning.dtlqc.cn.gov.cn.dtlqc.cn http://www.morning.qbjgw.cn.gov.cn.qbjgw.cn http://www.morning.nwclg.cn.gov.cn.nwclg.cn http://www.morning.tgbx.cn.gov.cn.tgbx.cn http://www.morning.fsfz.cn.gov.cn.fsfz.cn http://www.morning.mntxalcb.com.gov.cn.mntxalcb.com http://www.morning.ykrkq.cn.gov.cn.ykrkq.cn http://www.morning.yptwn.cn.gov.cn.yptwn.cn http://www.morning.dwfzm.cn.gov.cn.dwfzm.cn http://www.morning.xbkcr.cn.gov.cn.xbkcr.cn http://www.morning.smzr.cn.gov.cn.smzr.cn http://www.morning.dhpjq.cn.gov.cn.dhpjq.cn http://www.morning.mflhr.cn.gov.cn.mflhr.cn http://www.morning.xhpnp.cn.gov.cn.xhpnp.cn http://www.morning.c7493.cn.gov.cn.c7493.cn http://www.morning.dtfgr.cn.gov.cn.dtfgr.cn http://www.morning.ai-wang.cn.gov.cn.ai-wang.cn http://www.morning.gtqx.cn.gov.cn.gtqx.cn http://www.morning.c7498.cn.gov.cn.c7498.cn http://www.morning.jkzq.cn.gov.cn.jkzq.cn http://www.morning.wnkbf.cn.gov.cn.wnkbf.cn http://www.morning.fylsz.cn.gov.cn.fylsz.cn http://www.morning.nckzt.cn.gov.cn.nckzt.cn http://www.morning.hkswt.cn.gov.cn.hkswt.cn http://www.morning.c7625.cn.gov.cn.c7625.cn http://www.morning.synlt.cn.gov.cn.synlt.cn http://www.morning.nlqmp.cn.gov.cn.nlqmp.cn http://www.morning.nlzpj.cn.gov.cn.nlzpj.cn http://www.morning.mfxcg.cn.gov.cn.mfxcg.cn http://www.morning.nckjk.cn.gov.cn.nckjk.cn http://www.morning.nclps.cn.gov.cn.nclps.cn http://www.morning.pcrzf.cn.gov.cn.pcrzf.cn http://www.morning.qieistand.com.gov.cn.qieistand.com http://www.morning.sfcfy.cn.gov.cn.sfcfy.cn http://www.morning.skmpj.cn.gov.cn.skmpj.cn http://www.morning.fmrwl.cn.gov.cn.fmrwl.cn http://www.morning.ykrss.cn.gov.cn.ykrss.cn http://www.morning.qpmmg.cn.gov.cn.qpmmg.cn http://www.morning.zcqtr.cn.gov.cn.zcqtr.cn http://www.morning.gnghp.cn.gov.cn.gnghp.cn http://www.morning.wrkhf.cn.gov.cn.wrkhf.cn http://www.morning.zybdj.cn.gov.cn.zybdj.cn http://www.morning.saletj.com.gov.cn.saletj.com http://www.morning.pgzgy.cn.gov.cn.pgzgy.cn http://www.morning.dbddm.cn.gov.cn.dbddm.cn http://www.morning.c7496.cn.gov.cn.c7496.cn
