leetcode

commit 6919fb5e22d4a209a865b67c021d8a90497fd499
parent e122f6413731e67a59aeb2f0d858b1825fd21376
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 15 Oct 2023 23:06:52 +0000

Daily Problem

Diffstat:
A
Problems/1269.cpp
 | 
43
+++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 44 insertions(+), 0 deletions(-)
diff --git a/Problems/1269.cpp b/Problems/1269.cpp
@@ -0,0 +1,43 @@
+// Top-down DP
+class Solution {
+    static const int MOD = 1E9 + 7;
+    int dp[501][501];
+
+  public:
+    Solution() { memset(dp, 0xFF, sizeof(dp)); }
+    int numWays(const int steps, const int arrLen, const int crnt = 0) {
+        if (steps == 0) return crnt == 0;
+        if (dp[crnt][steps] != -1) return dp[crnt][steps];
+
+        int res = numWays(steps - 1, arrLen, crnt);
+        if (crnt > 0) res = (res + numWays(steps - 1, arrLen, crnt - 1)) % MOD;
+        if (crnt < arrLen - 1) res = (res + numWays(steps - 1, arrLen, crnt + 1)) % MOD;
+
+        return dp[crnt][steps] = res;
+    }
+};
+
+// Space optimized, bottom-up DP
+class Solution {
+    static const int MOD = 1E9 + 7;
+    static int dp[501], pdp[501];
+
+  public:
+    int numWays(const int steps, int arrLen) {
+        memset(pdp, 0x00, sizeof(pdp));
+        arrLen = min(arrLen, steps), pdp[0] = 1;
+        for (int remain = 1; remain <= steps; remain++) {
+            for (int crnt = arrLen - 1; crnt >= 0; crnt--) {
+                int res = pdp[crnt];
+                if (crnt > 0) res = (res + pdp[crnt - 1]) % MOD;
+                if (crnt < arrLen - 1) res = (res + pdp[crnt + 1]) % MOD;
+                dp[crnt] = res;
+            }
+            swap(dp, pdp);
+        }
+        return pdp[0];
+    }
+};
+
+int Solution::dp[501];
+int Solution::pdp[501];
diff --git a/README.md b/README.md
@@ -552,6 +552,7 @@ for solving problems.
 |  1254  |   Medium   | [Number of Closed Islands](Problems/1254.cpp)                                                      |
 |  1261  |   Medium   | [Find Elements in a Contaminated Binary Tree](Problems/1261.cpp)                                   |
 |  1268  |   Medium   | [Search Suggestions System](Problems/1268.cpp)                                                     |
+|  1269  |    Hard    | [Number of Ways to Stay in the Same Place After Some Steps](Problems/1269.cpp)                     |
 |  1277  |   Medium   | [Count Square Submatrices with All Ones](Problems/1277.cpp)                                        |
 |  1282  |   Medium   | [Group the People Given the Group Size They Belong To](Problems/1282.cpp)                          |
 |  1286  |   Medium   | [Iterator for Combination](Problems/1286.cpp)                                                      |