3.暴力去for和使用递归函数以及剪枝解决不了才考虑动态规划

221. 最大正方形

• 暴力正确但超时-76 / 81

func maximalSquare(matrix [][]byte) int {
    // 1 <= m, n 
    lenX := len(matrix)
    lenY := len(matrix[0])
    
    // 定了天的正方形的边长只能是lenX和lenY中最小的部分
    maybeMax := lenX
    if lenY < lenX {
        maybeMax = lenY
    }
    
    resEdgeLen := 0
    // 暴力遍历，使用斜对角线而已
    for leftTopX := 0 ; leftTopX < lenX; leftTopX++ {
        for leftTopY := 0; leftTopY < lenY; leftTopY++ {
            for edgeLen := 1; edgeLen <= maybeMax; edgeLen++ {
                if JudgeIsOK(matrix, leftTopX, leftTopY, 
                    leftTopX+edgeLen, leftTopY+edgeLen) && edgeLen > resEdgeLen {
                    resEdgeLen = edgeLen 
                }
            }
        }
    }

    return resEdgeLen * resEdgeLen
}

// 无论x还是y都是左闭右开
func JudgeIsOK(matrix [][]byte, 
    leftTopX int, leftTopY int, 
    rightDownX int , rightDownY int) bool{
    if rightDownX > len(matrix) {
        return false
    }
    if rightDownY > len(matrix[0]) {
        return false
    }

    for i := leftTopX ; i < rightDownX ; i++ {
        for j := leftTopY ; j < rightDownY ; j++ {
            if matrix[i][j] == byte('0') {
                return false
            }
        }
    }
    return true
}

• 暴力+剪枝1下，还是超时77 / 81

func maximalSquare(matrix [][]byte) int {
    // 1 <= m, n 
    lenX := len(matrix)
    lenY := len(matrix[0])
    
    // 定了天的正方形的边长只能是lenX和lenY中最小的部分
    maybeMax := lenX
    if lenY < lenX {
        maybeMax = lenY
    }
    
    resEdgeLen := 0
    // 暴力遍历，使用斜对角线而已
    for leftTopX := 0 ; leftTopX < lenX; leftTopX++ {
        for leftTopY := 0; leftTopY < lenY; leftTopY++ {
            for edgeLen := resEdgeLen+1; edgeLen <= maybeMax; edgeLen++ {
                if JudgeIsOK(matrix, leftTopX, leftTopY, 
                    leftTopX+edgeLen, leftTopY+edgeLen){
                    resEdgeLen = edgeLen 
                }
            }
        }
    }

    return resEdgeLen * resEdgeLen
}

// 无论x还是y都是左闭右开
func JudgeIsOK(matrix [][]byte, 
    leftTopX int, leftTopY int, 
    rightDownX int , rightDownY int) bool{
    if rightDownX > len(matrix) {
        return false
    }
    if rightDownY > len(matrix[0]) {
        return false
    }

    for i := leftTopX ; i < rightDownX ; i++ {
        for j := leftTopY ; j < rightDownY ; j++ {
            if matrix[i][j] == byte('0') {
                return false
            }
        }
    }
    return true
}

func Max(x int , y int) int {
    if x > y {
        return x
    }
    return y
}

实在无法继续剪枝了，那就看能不能构造出dp吧

func maximalSquare(matrix [][]byte) int {
    // 1 <= m, n 
    lenX := len(matrix)
    lenY := len(matrix[0])

    // 定义：dp[i][j]表示使用这个点作为正方形的右下方能形成的正方形的最大边长
    resEdgeLen := 0 
    // 语法！学习学习！！
    dp := make([][]int, lenX)
    for i := range dp {
        dp[i] = make([]int, lenY)
    }

    // 初始化第1行和第1列
    for j := 0 ; j < lenY ; j++ {
        if matrix[0][j] == byte('1') {
            dp[0][j] = 1
            resEdgeLen = 1
        }
    }
    for i := 0 ; i < lenX ; i++ {
        if matrix[i][0] == byte('1') {
            dp[i][0] = 1
            resEdgeLen = 1
        }
    }

    // 遍历顺序是，x变换最慢在外边，y最快
    for i := 1 ; i < lenX ; i++ {
        for j := 1 ; j < lenY ; j++ {
            if matrix[i][j] == byte('0') {
                dp[i][j] = 0
            } else {
                dp[i][j] = Min(Min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1
                resEdgeLen = Max(resEdgeLen,dp[i][j])
                
            }
        }
    }

    return resEdgeLen * resEdgeLen
}



func Max(x int , y int) int {
    if x > y {
        return x
    }
    return y
}

func Min(x int , y int) int {
    if x < y {
        return x
    }
    return y
}