C++||Explained Detailed||DP-prefix sum
!!!Please upvote if you like it..\nThe given question ask to count the number of sub-matrix whose sum of all element is equal to target value.\n\uD83D\uDE2E\u20
**!!!Please upvote if you like it..**\nThe given question ask to `count the number of sub-matrix whose sum of all element is equal to target value.`\n\uD83D\uDE2E\u200D\uD83D\uDCA8\uD83D\uDE2E\u200D\uD83D\uDCA8\uD83D\uDE2E\u200D\uD83D\uDCA8\uD83D\uDE2E\u200D\uD83D\uDCA8\n**How to find all sub-matrix??**\n->Let\'s think about 1-d array when we ask to f`ind all possible sub array we use prefix sum and do it `easily....\n**Here is a case of 2-D matrix..**\nIDEA:\uD83D\uDCAF\n1.To use 2D-prefix sum to store sum of all sub-matrix .\n2.Generate all  possible sub matrix-cordinate and find sum  and count possible value.\n3.Checking will be of O(1) time.\n\n`1.How to create 2-d prefix sum??`\n[![image](https://assets.leetcode.com/users/images/77f26df6-deac-4287-ac58-a6de3b77fd85_1642519275.3614054.jpeg)\n` 2.Genrating all possible submatrix co-rdinate:`\nThis can be done using 4-loops that  help to all sub-matrix.\n```\nclass Solution {\npublic:\n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {\n        \n        int n=matrix.size();\n        int m=matrix[0].size();\n        int dp[n+1][m+1];//2-ddp for prefix sum\n       \n       \n        for(int i=0;i<=n;i++)\n        {\n            for(int j=0;j<=m;j++)\n            {\n                if(i==0||j==0)\n                {\n                    dp[i][j]=0;\n                }\n                else{\n                    \n                dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+matrix[i-1][j-1];//using prefix dp formulae\n                    \n                }\n            }\n        }\n        int count=0;\n\t\t//generate all possible sub matrix.\n        for(int i=1;i<=n;i++)\n        {\n            for(int j=1;j<=m;j++)\n            {\n                for(int k=i;k<=n;k++)\n                {\n                    for(int l=j;l<=m;l++)\n                    {\n                      int ans=dp[i-1][j-1]+dp[k][l]-dp[i-1][l]-dp[k][j-1];\n                        if(ans==target)\n                        {\n                            count++;\n                        }\n                    }\n                    \n                }\n                \n            }\n        }\n        return count;\n       \n        \n        \n    }\n};\n```\n\n\n\n\n
['Dynamic Programming', 'C']