[Javascript] DP solution with explanation O(N*M)
The general idea is to walk through the array, and keep track of how many squares we have up to the current point.\nCounting squares of one is pretty straightfo
The general idea is to walk through the array, and keep track of how many squares we have up to the current point.\nCounting squares of one is pretty straightforward, but when it comes to summing the larger ones as well you might have had a little trouble thinking of the logic.\nIf we have a square of one, we know it\'s a square of one because of the `1` value in the cell of the matrix. We can apply this logic to find larger squares.\n\nExample 2x2 square:\n`1` `1`\n`1` `1`  **square count**: 5 (**4**1x1 (single) squares, and **1** 2x2 square)\nIf we just add 1 for each single square, we\'d only get 4. The key is to look back at past values to see what the new sum will be.\nAt each square we can find it\'s largest possible square with this logic `Math.min(A[i-1][j], A[i-1][j-1], A[i][j-1])`. We look left, up-left, and up to find the number of squares at each of those positions and take the minimum. After we\'ve found the minimum of previous squares, we will simply add 1 to that for the current square.\nIn the 2x2 example, when we reach the bottom right square, our lookback logic will be `Math.min(1, 1, 1)` so we would have `1` as the previous square count and we\'d add `1` for the current square to give us `2`.\n\nThe result matrix (if we stored our count at each level) would be\n`1` `1`\n`1` `2` \nWhich sums up to the correct answer: 5.\n\n```\n * @return {number}\n */\nvar countSquares = function(matrix) {\n    let count = 0;\n    // Initialize length vars for clarity in loop (instead of j < matrix[i].length)\n    let M = matrix.length, N = matrix[0].length;\n    for (let i = 0; i < M; i++) {\n        for (let j = 0; j < N; j++) {\n            // Only do stuff when matrix[i][j] evaluates to true (meaning it has a 1)\n            if (matrix[i][j]) {\n                // i && j will be true once we\'re past the first row & column.\n                // if not we just do 1 + 0 because there\' cant be more than one square when width or heigh of square is just 1\n                \n                // Once i & j are both > 0, we will check the minimum value from left, up-left, and up indices in\n\t\t\t\t// the matrix\n                matrix[i][j] = 1 + (i && j ? Math.min(matrix[i][j-1], matrix[i-1][j-1], matrix[i-1][j]) : 0)\n                // After saving the amount of squares up to this point, increment the count sum by that much\n                count += matrix[i][j]\n            }\n        }\n    }\n    return count;\n};\n```
[]