leetcode

commit ec6d4815de18f268837c49c4804d9964b2b005cb
parent 904b8535aa3a8d77387ade201b070040aaa3d293
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 22 Jul 2023 23:23:44 +0200

Daily Problem

Diffstat:
A
Problems/0688.cpp
 | 
25
+++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 26 insertions(+), 0 deletions(-)
diff --git a/Problems/0688.cpp b/Problems/0688.cpp
@@ -0,0 +1,25 @@
+class Solution {
+  bool valid(int n, int x, int y) { return x >= 0 && y >= 0 && x < n && y < n; }
+
+  double dp[25][25][101];
+
+public:
+  double knightProbability(int n, int k, int row, int column) {
+    static const int offset_x[] = {-2, -2, -1, 1, 2, 2, 1, -1};
+    static const int offset_y[] = {-1, 1, 2, 2, 1, -1, -2, -2};
+
+    if (!k) return 1;
+    if (dp[row][column][k]) return dp[row][column][k];
+
+    double res = 0;
+    for (int i = 0; i < 8; i++) {
+      int x = row + offset_x[i];
+      int y = column + offset_y[i];
+
+      if (!valid(n, x, y)) continue;
+      res += 0.125 * knightProbability(n, k - 1, x, y);
+    };
+
+    return dp[row][column][k] = res;
+  }
+};
diff --git a/README.md b/README.md
@@ -329,6 +329,7 @@ for solving problems.
 |  0671  |    Easy    | [Second Minimum Node In a Binary Tree](Problems/0671.cpp)                                        |
 |  0673  |   Medium   | [Number of Longest Increasing Subsequence](Problems/0673.cpp)                                    |
 |  0684  |   Medium   | [Redundant Connection](Problems/0684.cpp)                                                        |
+|  0688  |   Medium   | [Knight Probability in Chessboard](Problems/0688.cpp)                                            |
 |  0692  |   Medium   | [Top K Frequent Words](Problems/0692.cpp)                                                        |
 |  0695  |   Medium   | [Max Area of Island](Problems/0695.cpp)                                                          |
 |  0700  |    Easy    | [Search in a Binary Search Tree](Problems/0700.cpp)                                              |