C++ DP with explanation
\nclass Solution {\npublic:\n    double knightProbability(int N, int K, int r, int c) {\n        // DP: define dp[N][N] where dp[i][j] is the probability of sta
```\nclass Solution {\npublic:\n    double knightProbability(int N, int K, int r, int c) {\n        // DP: define dp[N][N] where dp[i][j] is the probability of staying on the board by K moves.\n        // We cannot get the probability of K moves immediately, so compute from K == 0 where dp[i][j] = 1.\n        //\n        // Then for each k <= K, we have the following formula:\n        // 1) Get the probabilities of all 8 moves from (i, j), aka dp[i][j].\n        // 2) Sum them up, and divide the result by 8 because of randomness.\n        // 3) The probability of new_dp[i][j] = (sum in #2) / 8.\n        //\n        // Finally return the ultimate dp[r][c] after K iterations.\n        vector<vector<double>> dp(N, vector<double>(N, 1));\n        for (int k = 1; k <= K; ++k)\n        {\n            vector<vector<double>> newDP(N, vector<double>(N));\n            for (int i = 0; i < N; ++i)\n            {\n                for (int j = 0; j < N; ++j)\n                {\n                    double total = 0;\n                    total += i >= 2 && j >= 1 ? dp[i - 2][j - 1] : 0;\n                    total += i >= 2 && j + 1 < N ? dp[i - 2][j + 1] : 0;\n                    total += i >= 1 && j >= 2 ? dp[i - 1][j - 2] : 0;\n                    total += i >= 1 && j + 2 < N ? dp[i - 1][j + 2] : 0;\n                    total += i + 1 < N && j >= 2 ? dp[i + 1][j - 2] : 0;\n                    total += i + 1 < N && j + 2 < N ? dp[i + 1][j + 2] : 0;\n                    total += i + 2 < N && j >= 1 ? dp[i + 2][j - 1] : 0;\n                    total += i + 2 < N && j + 1 < N ? dp[i + 2][j + 1] : 0;\n                    \n                    newDP[i][j] = total / 8;\n                }\n            }\n            \n            dp = newDP;\n        }\n        \n        return dp[r][c];\n    }\n};\n```
[]