Welcome to Joey’sTech.
On this day and from this video, you are going to learn how to solve an amazing matrix problem using dynamic programming.
The problem belongs to my Leetcode series hence, it goes without saying that I have taken it from Leetcode.
The problem goes by the title - ‘Count Submatrices With All Ones’.
Without further delay, let’s check out its problem statement.
You are given a matrix of m x n dimensions.
The matrix contains only 1s and 0s.
You need to find out how many sub-matrices exist which carry all ones.
1 , 0 , 1
1, 1, 0
1, 1, 0
If you see this matrix then various sub-matrices of different dimensions exist.
This highlighted one represents a submatrix of 2 x 1 i.e. two rows and 1 column. Here is another sub-matrix of 2 x 2 that contains all 1s.
We need to find out how many such sub-matrices exist?
So, let us begin solving this problem, but before that, I request you to subscribe to my channel and press the bell icon to not miss out on any of the videos I release in the future.
Github link to the Java solution
https://github.com/joeystech2020/dynamicprogramming/blob/4bd1b96017c0064a2daf92d46501d4bf3043ea01/countsubmatriceswithone
