solution for matrix problem

SouvikDcoder · SouvikDcoder · commit 338313db4e95 · 2022-10-16T12:55:39.000+05:30
diff --git a/leetcode_kuro_RnD.ipynb b/leetcode_kuro_RnD.ipynb
@@ -8968,12 +8968,34 @@
     },
     {
       "cell_type": "code",
-      "execution_count": null,
+      "execution_count": 9,
       "metadata": {},
-      "outputs": [],
+      "outputs": [
+        {
+          "name": "stdout",
+          "output_type": "stream",
+          "text": [
+            "2\n"
+          ]
+        }
+      ],
       "source": [
         "# https://leetcode.com/problems/paths-in-matrix-whose-sum-is-divisible-by-k\n",
-        "\n"
+        "# solution : https://leetcode.com/problems/paths-in-matrix-whose-sum-is-divisible-by-k/discuss/2678950/Python-DP-solution\n",
+        "import collections\n",
+        "from typing import Counter\n",
+        "\n",
+        "A = [[5,2,4],[3,0,5],[0,7,2]]\n",
+        "k = 3\n",
+        "\n",
+        "n, m, mod = len(A), len(A[0]), 10**9 + 7\n",
+        "dp = [Counter() for j in range(m + 1)]\n",
+        "dp[0][0] = 1\n",
+        "for i, r in enumerate(A):\n",
+        "    for j, a in enumerate(r):\n",
+        "        dp[j] = Counter({(a + b) % k: c % mod for b, c in (dp[j] + dp[j-1]).items()})\n",
+        "print(dp[m - 1][0])\n",
+        "#return dp[m - 1][0]"
       ]
     }
   ],
