🎨 The ART of Dynamic Programming
\uD83C\uDFA8 The ART of Dynamic Programming: perform a linear scan of the input matrix A.  Each cell i,j of A is a square submatrix of size 1 if and only if the
[\uD83C\uDFA8 The ART of Dynamic Programming:](https://leetcode.com/discuss/general-discussion/712010/The-ART-of-Dynamic-Programming-An-Intuitive-Approach%3A-from-Apprentice-to-Master) perform a linear scan of the input matrix `A`.  Each cell `i`,`j` of `A` is a square submatrix of size `1` if and only if the value `A[i][j] = 1`.  Consider appending onto the bottom-right corner of submatrices of size `1` to create submatrices of size `2` (etc. etc...) via the recurrence relation:\n\n`dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])`\n\nThat is, for the bottom-right corner of each candidate submatrix, we consider the minimum value of the adjacent cells above, to-the-left, and above-and-to-the-left and add `1` onto it, attempting for form larger and larger submatrices.  Then return the accumulated sum of the DP matrix as the answer.\n\n---\n\n*Example 1:*\n```\nInput: A =\n[\n  [0,1,1,1],\n  [1,1,1,1],\n  [0,1,1,1]\n]\n\nOutput: dp =\n[\n  [0,1,1,1],\n  [1,1,2,2],\n  [0,1,2,3]\n]\n0 + 1 + 1 + 1 = 3\n1 + 1 + 2 + 2 = 6\n0 + 1 + 2 + 3 = 6\nAnswer = 3 + 6 + 6 = 15\n```\n\n*Example 2:*\n```\nInput: A = \n[\n  [1,0,1],\n  [1,1,0],\n  [1,1,0]\n]\n\nOutput: dp = \n[\n  [1,0,1],\n  [1,1,0],\n  [1,2,0]\n]\n1 + 0 + 1 = 2\n1 + 1 + 0 = 2\n1 + 2 + 0 = 3\nAnswer = 2 + 2 + 3 = 7\n```\n\n---\n\n*Kotlin*\n```\nclass Solution {\n    fun countSquares(A: Array<IntArray>): Int {\n        var (M, N) = Pair(A.size, A[0].size)\n        var dp = A.map{ it.copyOf() }\n        for (i in 1 until M)\n            for (j in 1 until N)\n                if (A[i][j] == 1)\n                    dp[i][j] = 1 + listOf(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]).min()!!\n        return dp.map{ it.sum() }.sum()\n    }\n}\n```\n\n*Javascript*\n```\nlet countSquares = A => {\n    let [M, N] = [A.length, A[0].length];\n    let dp = [...A].map(row => [...row]);\n    for (let i = 1; i < M; ++i)\n        for (let j = 1; j < N; ++j)\n            if (A[i][j])\n                dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);\n    return _.sum(dp.map(row => _.sum(row)));\n};\n```\n\n*Python3*\n```\nclass Solution:\n    def countSquares(self, A: List[List[int]]) -> int:\n        M, N = len(A), len(A[0])\n        dp = [row[:] for row in A]\n        for i in range(1, M):\n            for j in range(1, N):\n                if A[i][j]:\n                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])\n        return sum(sum(row) for row in dp)\n```\n\n*C++*\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    using VVI = vector<VI>;\n    int countSquares(VVI& A) {\n        int M = A.size(),\n            N = A[0].size();\n        auto dp{ A };\n        for (auto i{ 1 }; i < M; ++i)\n            for (auto j{ 1 }; j < N; ++j)\n                if (A[i][j])\n                    dp[i][j] = 1 + min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] });\n        return accumulate(dp.begin(), dp.end(), 0, [](auto t, auto& row) {\n            return t + accumulate(row.begin(), row.end(), 0);\n        });\n    }\n};\n```
[]