动态规划专栏
动态规划专栏
YxinMiracle动态规划作题总结
- 统计X和Y频数相等的子矩阵数量 - 405场周赛Q3 【前缀和+动态规划】
题目一:统计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 | int[][] dpX = new int[grid.length + 1][grid[0].length + 1]; |
然后我们经过观察可以发现,我们动态规划的推导式为:
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 | public int numberOfSubmatrices(char[][] grid) { |
一次通过,直接完成