✅DP + Memoization ||  JAVA/C++/Python  Beginner Friendly🔥🔥🔥
Approach\nThe knightProbability function initializes a memoization array memo, and then calls the recursive function dp. The dp function calculates the probabil
# Approach\nThe `knightProbability` function initializes a memoization array `memo`, and then calls the recursive function `dp`. The dp function calculates the probability of the knight remaining on the board after k moves from a given position. It considers all eight possible moves and recursively calls itself for each move with reduced k and updated position. The probabilities are stored in the memo array to avoid redundant computations. Finally, the function returns the probability of the knight remaining on the board after k moves, starting from the given position. The time complexity is O(k * n^2), and the space complexity is O(k * n^2) due to the memoization array.\nWhen we **return** the original code should be return `(possibleCellCounts/8)*(sum/possibleCellCounts)` then we simplify it to `sum/8`.\n\nExaample: `n = 3, k = 2, row = 0, column = 0`\n- for the first move the probability for the knight that remains on the board is  `2/8`\n- for the second move we need to consider for those two cells([1,2], [2,1]) and for both of the cells th probability is `2/8`. So, (2/8 + 2/8)/8 => 1/16 = 0.06250\n```java []\npublic class Solution {\n    private double[][][] memo;\n\n    public double knightProbability(int n, int k, int row, int column) {\n        this.memo = new double[k + 1][n][n];\n        return dp(n, k, row, column);\n    }\n\n    private double dp(int n, int k, int row, int column) {\n        if (k == 0) return 1.0;\n        if (memo[k][row][column] != 0) return memo[k][row][column];\n\n        double sum = 0;\n        int[][] moves = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};\n        for (int[] move : moves) {\n            int r = row + move[0];\n            int c = column + move[1];\n            if (r >= 0 && r < n && c >= 0 && c < n) {\n                sum += dp(n, k - 1, r, c);\n            }\n        }\n\n        memo[k][row][column] = sum / 8;\n        return sum / 8;\n    }\n}\n\n```\n```python []\ndef knightProbability(n, k, row, column):\n    memo = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(k + 1)]\n    return dp(n, k, row, column, memo)\n\ndef dp(n, k, row, column, memo):\n    if k == 0:\n        return 1.0\n    if memo[k][row][column] != 0:\n        return memo[k][row][column]\n    \n    sum_prob = 0\n    moves = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]\n    for dr, dc in moves:\n        nr, nc = row + dr, column + dc\n        if 0 <= nr < n and 0 <= nc < n:\n            sum_prob += dp(n, k - 1, nr, nc, memo)\n\n    memo[k][row][column] = sum_prob / 8\n    return sum_prob / 8\n\n```\n```C++ []\nclass Solution {\npublic:\n    double knightProbability(int n, int k, int row, int column) {\n        vector<vector<vector<double>>> memo(k + 1, vector<vector<double>>(n, vector<double>(n, 0)));\n        return dp(n, k, row, column, memo);\n    }\n    \n    double dp(int n, int k, int row, int column, vector<vector<vector<double>>>& memo) {\n        if (k == 0) {\n            return 1.0;\n        }\n        if (memo[k][row][column] != 0) {\n            return memo[k][row][column];\n        }\n        \n        double sum_prob = 0;\n        vector<pair<int, int>> moves = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};\n        for (auto move : moves) {\n            int nr = row + move.first;\n            int nc = column + move.second;\n            if (nr >= 0 && nr < n && nc >= 0 && nc < n) {\n                sum_prob += dp(n, k - 1, nr, nc, memo);\n            }\n        }\n        \n        memo[k][row][column] = sum_prob / 8;\n        return sum_prob / 8;\n    }\n};\n\n```\n\n\n# Complexity\n- Time/Space complexity:\nO(k * n^2)\n\n# *Upvote would be appreciated!*\n\n\n```
['Dynamic Programming', 'Memoization', 'C++', 'Java', 'Python3']