C++ DP 2 methods: Bottom-up and Top-down (Easy to understand and clean)
\nclass Solution {\npublic:\n    // Bottom-up\n    // Time: O(N^2 * k)\n    // Space: O(N^2 * k)\n    double knightProbability(int N, int K, int r, int c) {\n  
```\nclass Solution {\npublic:\n    // Bottom-up\n    // Time: O(N^2 * k)\n    // Space: O(N^2 * k)\n    double knightProbability(int N, int K, int r, int c) {\n        unordered_map<string, double> dp;\n        for (int i = 0; i <= K; i++) {\n            for (int j = 0; j < N; j++) {\n                for (int k = 0; k < N; k++) {\n                    for (auto dir : dirs) {\n                        int new_j = j + dir[0];\n                        int new_k = k + dir[1];\n                        string key = to_string(i) + "#" + to_string(j) + "#" + to_string(k);\n                        string key2 = to_string(i - 1) + "#" + to_string(new_j) + "#" + to_string(new_k);\n                        if (i == 0) dp[key] = 1.0;\n                        else if (new_j >= 0 && new_j < N && new_k >= 0 && new_k < N)\n                            dp[key] += (1 / 8.0) * dp[key2];\n                        \n                    }\n                }\n            }\n        }\n        string key = to_string(K) + "#" + to_string(r) + "#" + to_string(c);\n        return dp[key];\n    }\nprivate:    \n    vector<vector<int>> dirs =\n        {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};\n};\n\n\nclass Solution2 {\npublic:\n    // Top-down\n    // Time: O(N^2 * k)\n    // Space: O(N^2 * k)\n    double knightProbability(int N, int K, int r, int c) {\n        return helper(N, K, r, c);\n    }\n    double helper(int N, int K, int r, int c) {\n        if (r >= N || r < 0 || c >= N || c < 0) return 0.0;\n        if (K == 0) return 1.0;\n        string key = to_string(K) + "#" + to_string(r) + "#" + to_string(c);\n        if (dp.count(key)) return dp[key];\n        double res = 0;\n        for (auto dir : dirs) {\n            int new_r = r + dir[0];\n            int new_c = c + dir[1];\n            res += (1 / 8.0) * helper(N, K - 1, new_r, new_c);\n        }\n        dp[key] = res;\n        return res;\n    }\nprivate:\n    unordered_map<string, double> dp;\n    vector<vector<int>> dirs =\n        {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};\n};\n```
[]