动态规划专栏

动态规划作题总结

题目一：统计X和Y瓶数相等的子矩阵数量

这个题目是在第405场周赛中遇见，作为Q3，当初一开始纠结的一点是我如何才能够选到合适的子矩阵，会不会出现畸形。后面经过观察发现，原来每一个大矩阵中的每一个方块都可以作为子矩阵的情况。

上述的这个问题解决完了之后，下一个问题就是我们如何才可以快速的去计算出这个子矩阵中，X和Y的个数有多少个呢？通过发现我们可以观察到，2*2的矩阵中含有X或者Y的情况是会利用到1*1矩阵的结果的，那么我们是不是可以利用前缀和+动态规划的方式进行计算呢？

有了这样的想法之后，就需要来看看我们怎么样可以进行计算了，一开始先进行分析。

x y .
Y . .

对于上面这个2*3的矩阵，行数我们记成n，列数我们记成m。我们是不是可以先初始化一个n+1*m+1的一个矩阵，其中第0行和第0列我们初始化为0，便于我们后续的操作。然后我们开始进行迭代。

我们用两个数组，来分别计算X和Y的数量，dpX[i][j]表示，对于X而言，i和j表示在源矩阵的这个位置中含有多少个x。对于Y来说也一样。

首先是先进行初始化，然后使用双层循环去一个个迭代

1
2
3
4
5
6
7
8
int[][] dpX = new int[grid.length + 1][grid[0].length + 1];
int[][] dpY = new int[grid.length + 1][grid[0].length + 1];

for (int i = 1; i <= grid.length; i++) {
    for (int j = 1; j <= grid[0].length; j++) {
		xxxx
    }
 }

然后我们经过观察可以发现，我们动态规划的推导式为：

1
dpX[i][j] = dpX[i - 1][j] + dpX[i][j - 1] - dpX[i - 1][j - 1] + 1;

不过要强调一个点：其他情况下的状态也需要进行转移，只不过是不需要+1

1
dpX[i][j] = dpX[i - 1][j] + dpX[i][j - 1] - dpX[i - 1][j - 1];

有了这个推导式之后，后面就简单了，完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int numberOfSubmatrices(char[][] grid) {

    int[][] dpX = new int[grid.length + 1][grid[0].length + 1];
    int[][] dpY = new int[grid.length + 1][grid[0].length + 1];

    for (int i = 1; i <= grid.length; i++) {
        for (int j = 1; j <= grid[0].length; j++) {
            char c = grid[i - 1][j - 1];
            dpX[i][j] = dpX[i - 1][j] + dpX[i][j - 1] - dpX[i - 1][j - 1];
            dpY[i][j] = dpY[i - 1][j] + dpY[i][j - 1] - dpY[i - 1][j - 1];
            if (c == 'X') {
                dpX[i][j] = dpX[i][j] + 1;
            }
            if (c == 'Y') {
                dpY[i][j] = dpY[i][j] + 1;
            }
        }
    }
    int res = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (dpX[i + 1][j + 1] == dpY[i + 1][j + 1] && dpX[i + 1][j + 1] >= 1) {
                res++;
            }
        }
    }
    return res;
}

一次通过，直接完成

image-20240719112112994
image-20240719112112994