[백준] 1915 - 가장 큰 정사각형 (JAVA)

dp 점화식 구하기 세상 어렵다,,,

import java.io.*;
import java.util.*;

public class Main {
    static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer tokenizer = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(tokenizer.nextToken());
        int M = Integer.parseInt(tokenizer.nextToken());
        arr = new int[N][M];

        for (int i = 0; i < N; i++) {
            String[] split = br.readLine().split("");
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(split[j]);
            }
        }
        br.close();

        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                int dp = dp(i, j);
                arr[i][j] = dp;
                max = Math.max(dp, max);
            }
        }

        bw.write(String.valueOf(max * max ));
        bw.flush();
        bw.close();
    }

    static int dp(int i, int j){
        if(i == 0 || j == 0 || arr[i][j] == 0) { // 가장자리에 있는 애들
            return arr[i][j];
        }

        return Math.min(Math.min(arr[i-1][j], arr[i][j-1]), arr[i-1][j-1]) + 1;
    }
}