问题描述

　　小蓝有一个 100 行 100 列的矩阵，矩阵的左上角为 1。其它每个位置正好比其左边的数大 2，比其上边的数大 1 。

        例如，第 1 行第 2 列为 3，第 2 行第 2 列 为 4，第 10 行第 20 列为 48。 　　

        小蓝想在矩阵中找到一个由连续的若干行、连续的若干列组成的子矩阵，使得其和为 2022，请问这个子矩阵中至少包含多少个元素（即子矩阵的行数和列数的乘积）。

答案提交

　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

=========================================================================

import java.io.IOException;

public class Main0 {
    public static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        int[][] ss = new int[100][100];
        ss[0][0] = 1;
        for (int i = 1; i < 100; i++) {
            ss[i][0] = ss[i - 1][0] + 1;
            ss[0][i] = ss[0][i - 1] + 2;
        }
        for (int i = 1; i < 100; i++) {
            for (int j = 1; j < 100; j++) {
                ss[i][j] = ss[i][j - 1] + 2;
            }
        }
        int[][] dp = new int[100][100];
        updateDP(ss, dp);
        // 对每个点进行遍历
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                dfs(ss, dp, i, j);
            }
        }
        System.out.println();
    }

    private static void dfs(int[][] ss, int[][] dp, int x, int y) {
        int cur = ss[x][y] - 1;
        for (int xLen = 1; x + xLen < 100; xLen++) {
            for (int yLen = 1; y + yLen < 100; yLen++) {
                int mut = xLen * yLen;
                int temp = cur * mut + dp[xLen - 1][yLen - 1];
                if (temp > 2022) break;
                if (temp == 2022) {
                    min = Math.min(min, mut);
                    System.out.println("x:" + x);
                    System.out.println("y:" + y);
                    System.out.println("ss[x][y]:" + ss[x][y]);
                    System.out.println("xLen:" + xLen);
                    System.out.println("yLen:" + yLen);
                    System.out.println("min:" + min);
                    System.out.println("===================================================");
                }
            }
        }
    }

    private static void updateDP(int[][] ss, int[][] dp) {
        dp[0][0] = 1;
        for (int i = 1; i < 100; i++) {
            dp[i][0] = dp[i - 1][0] + ss[i][0];
            dp[0][i] = dp[0][i - 1] + ss[0][i];
        }
        for (int i = 1; i < 100; i++) {
            for (int j = 1; j < 100; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + ss[i][j];
            }
        }
    }
}