給你一個只包含 0 和 1 的 rows * columns 矩陣 mat ，請你返回有多少個 子矩形 的元素全部都是 1 。

示例 1：
輸入：mat =
[[1,0,1],
[1,1,0],
[1,1,0]]
輸出：13
解釋：
有 6 個 1x1 的矩形。
有 2 個 1x2 的矩形。
有 3 個 2x1 的矩形。
有 1 個 2x2 的矩形。
有 1 個 3x1 的矩形。
矩形數目總共 = 6 + 2 + 3 + 1 + 1 = 13 。

解題思路

數組含義：dp[i][j]位于（i，j）的元素向左延長的長度
狀態轉移：min= Math.min(dp[k][j],min) 向上遍歷，加入滿足最小長度的矩形

代碼

class Solution {public int numSubmat(int[][] mat) {int n=mat.length,m=mat[0].length,res=0;int[][]dp=new int[n][m+1];for(int i=0;i<n;i++)for(int j=1;j<=m;j++)dp[i][j]=mat[i][j-1]==1?dp[i][j-1]+1:0;for(int i=0;i<n;i++)for(int j=1;j<=m;j++){int min=Integer.MAX_VALUE;for (int k=i;k>=0;k--)if(dp[k][j]==0) break;else{min= Math.min(dp[k][j],min);res+=min;}}return res;}
}