leetcode

commit de45cf25b94c02c2f225e8b46103db0361147a4a
parent f99ee8906d052737b2dfcc137549cbf1c4a1358d
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon, 27 Nov 2023 21:04:59 +0000

Daily Problem

Diffstat:
A
Problems/0935.cpp
 | 
21
+++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 22 insertions(+), 0 deletions(-)
diff --git a/Problems/0935.cpp b/Problems/0935.cpp
@@ -0,0 +1,21 @@
+class Solution {
+    static const int MOD = 1e9 + 7;
+
+  public:
+    int knightDialer(int n) const {
+        static const vector<int> offsets[] = {{4, 6}, {8, 6},    {7, 9}, {4, 8}, {3, 9, 0},
+                                              {},     {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}};
+
+        vector<int> pdp(10, 1), dp(10);
+        for (int i = 1; i < n; i++) {
+            for (int j = 0; j < 10; j++) {
+                int res = 0;
+                for (const int prev : offsets[j])
+                    res = (res + pdp[prev]) % MOD;
+                dp[j] = res;
+            }
+            swap(dp, pdp);
+        }
+        return accumulate(begin(pdp), end(pdp), 0, [&](int a, int acc) { return (acc + a) % MOD; });
+    }
+};
diff --git a/README.md b/README.md
@@ -469,6 +469,7 @@ for solving problems.
 |  0932  |   Medium   | [Beautiful Array](Problems/0932.cpp)                                                               |
 |  0933  |    Easy    | [Number of Recent Calls](Problems/0933.cpp)                                                        |
 |  0934  |   Medium   | [Shortest Bridge](Problems/0934.cpp)                                                               |
+|  0935  |   Medium   | [Knight Dialer](Problems/0935.cpp)                                                                 |
 |  0938  |    Easy    | [Range Sum of BST](Problems/0938.cpp)                                                              |
 |  0941  |    Easy    | [Valid Mountain Array](Problems/0941.cpp)                                                          |
 |  0944  |    Easy    | [Delete Columns to Make Sorted](Problems/0944.cpp)                                                 |