leetcode

commit f252679f199e006e0fe4dcb5856ad198decb181e
parent d7b4c9307428ab7e40cc1da93fce311210572d8f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 28 Jul 2023 10:35:30 +0200

Daily Problem

Diffstat:
A
Problems/0486.cpp
 | 
20
++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 21 insertions(+), 0 deletions(-)
diff --git a/Problems/0486.cpp b/Problems/0486.cpp
@@ -0,0 +1,20 @@
+class Solution {
+  int dp[21][21];
+
+  int rec(const vector<int> &nums, int i, int j) {
+    if (i == j) return nums[i];
+    if (dp[i][j] != -1) return dp[i][j];
+
+    int left = nums[i] - rec(nums, i + 1, j);
+    int right = nums[j] - rec(nums, i, j - 1);
+
+    return dp[i][j] = max(left, right);
+  }
+
+public:
+  Solution() { memset(dp, 0xFF, sizeof(dp)); }
+
+  bool PredictTheWinner(const vector<int> &nums) {
+    return rec(nums, 0, nums.size() - 1) >= 0;
+  }
+};
diff --git a/README.md b/README.md
@@ -286,6 +286,7 @@ for solving problems.
 |  0460  |    Hard    | [LFU Cache](Problems/0460.cpp)                                                                   |
 |  0472  |    Hard    | [Concatenated Words](Problems/0472.cpp)                                                          |
 |  0485  |    Easy    | [Max Consecutive Ones](Problems/0485.cpp)                                                        |
+|  0486  |   Medium   | [Reachable Nodes With Restrictions](Problems/0486.cpp)                                           |
 |  0491  |   Medium   | [Non-decreasing Subsequences](Problems/0491.cpp)                                                 |
 |  0494  |   Medium   | [Target Sum](Problems/0494.cpp)                                                                  |
 |  0496  |   Medium   | [Next Greater Element I](Problems/0496.cpp)                                                      |