牛客NC108 最大正方形【中等 动态规划 Java,Go,PHP】

题目

题目链接：
https://www.nowcoder.com/practice/0058c4092cec44c2975e38223f10470e

思路

动态规划:
先初始化第一行和第一列。然后其他单元格依赖自己的上边，左边和左上角

参考答案Java

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 最大正方形* @param matrix char字符型二维数组* @return int整型*/public int solve (char[][] matrix) {// 动态规划://先初始化第一行和第一列。然后其他单元格依赖自己的上边，左边和左上角if (matrix == null || matrix.length == 0) return 0;int n = matrix.length;int m  =  matrix[0].length;int[][] dp = new int[n][m];int ans = 0;for (int j = 0; j < m ; j++) {if (matrix[0][j] == '1') {dp[0][j] = 1;ans = 1;}}for (int i = 0; i < n ; i++) {if (matrix[i][0] == '1') {dp[i][0] = 1;ans = 1;}}for (int i = 1; i < n ; i++) {for (int j = 1; j < m ; j++) {if (matrix[i][j] == '1') {int p1 = dp[i - 1][j - 1];int p2 = dp[i][j - 1];int p3 = dp[i - 1][j];int cur = p1;if (cur > p2) cur = p2;if (cur > p3) cur = p3;dp[i][j] = cur + 1;if (ans < dp[i][j]) {ans = dp[i][j];}}}}return ans * ans;}
}

参考答案Go

package main/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 最大正方形* @param matrix char字符型二维数组* @return int整型*/
func solve(matrix [][]byte) int {// 动态规划://先初始化第一行和第一列。然后其他单元格依赖自己的上边，左边和左上角if matrix == nil || len(matrix) == 0 {return 0}n := len(matrix)m := len(matrix[0])dp := make([][]int, n)for i := 0; i < n; i++ {dp[i] = make([]int, m)}ans := 0for j := 0; j < m; j++ {if matrix[0][j] == '1' {dp[0][j] = 1ans = 1}}for i := 0; i < n; i++ {if matrix[i][0] == '1' {dp[i][0] = 1ans = 1}}for i := 1; i < n; i++ {for j := 1; j < m; j++ {if matrix[i][j] == '1' {p1 := dp[i-1][j-1]p2 := dp[i][j-1]p3 := dp[i-1][j]cur := p1if cur > p2 {cur = p2}if cur > p3 {cur = p3}dp[i][j] = cur + 1if ans < cur+1 {ans = cur + 1}}}}return ans * ans
}

参考答案PHP

<?php/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 最大正方形* @param matrix char字符型二维数组 * @return int整型*/
function solve( $matrix )
{// 动态规划://先初始化第一行和第一列。然后其他单元格依赖自己的上边，左边和左上角if($matrix ==null || count($matrix) ==0) return 0;$n = count($matrix);$m = count($matrix[0]);$ans = 0;$dp = array();for ($j=0;$j<$m;$j++){if($matrix[0][$j] =='1'){$dp[0][$j] =1;$ans=1;}}for($i=0;$i<$n;$i++){if($matrix[$i][0] =='1'){$dp[$i][0] =1;$ans =1;}}for($i=1;$i<$n;$i++){for($j=1;$j<$m;$j++){if($matrix[$i][$j] =='1'){$p1 = $dp[$i-1][$j-1];$p2 = $dp[$i][$j-1];$p3 = $dp[$i-1][$j];$cur =$p1;if($cur > $p2)$cur = $p2;if($cur> $p3) $cur =$p3;$dp[$i][$j] = $cur+1;if($ans < $cur+1){$ans = $cur+1;}}}}return $ans*$ans;
}