Easy C++ DFS & 3D Memo->iterative 2D DP
Intuition\n Describe your first thoughts on how to solve this problem. \nUse the probability formula\n\nProb(i, j, move=k) \\=\sum_{(r,s)} Prob(i, j, move=k\Big
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse the probability formula\n$$\nProb(i, j, move=k) \\\\=\\sum_{(r,s)} Prob(i, j, move=k\\Big|_{(r,s)\\to(i, j)})Prob((r,s)\\to(i, j))\\\\\n=\n\\sum_{(r,s)}Prob(r, s, move=k-1)\\frac{1}{8}\n$$\nto implement recursive DFS with memo, that is DP!!\n# Approach\n<!-- Describe your approach to solving the problem. -->\n2nd approach is just a transform of recursion to iterative form. Due to updating  previous DP state array to the new one is proceeded at each move just once, the 3D DP state array can be reduced to 2D array!\n\nA list for n=8 dp state array for move=1,..8\n```\nmove:1\n      0.25\t,     0.375\t,       0.5\t,       0.5\t,       0.5\t,       0.5\t,     0.375\t,      0.25\t,\n     0.375\t,       0.5\t,      0.75\t,      0.75\t,      0.75\t,      0.75\t,       0.5\t,     0.375\t,\n       0.5\t,      0.75\t,         1\t,         1\t,         1\t,         1\t,      0.75\t,       0.5\t,\n       0.5\t,      0.75\t,         1\t,         1\t,         1\t,         1\t,      0.75\t,       0.5\t,\n       0.5\t,      0.75\t,         1\t,         1\t,         1\t,         1\t,      0.75\t,       0.5\t,\n       0.5\t,      0.75\t,         1\t,         1\t,         1\t,         1\t,      0.75\t,       0.5\t,\n     0.375\t,       0.5\t,      0.75\t,      0.75\t,      0.75\t,      0.75\t,       0.5\t,     0.375\t,\n      0.25\t,     0.375\t,       0.5\t,       0.5\t,       0.5\t,       0.5\t,     0.375\t,      0.25\t,\n\n===========\nmove:2\n    0.1875\t,   0.28125\t,  0.359375\t,   0.40625\t,   0.40625\t,  0.359375\t,   0.28125\t,    0.1875\t,\n   0.28125\t,     0.375\t,       0.5\t,  0.578125\t,  0.578125\t,       0.5\t,     0.375\t,   0.28125\t,\n  0.359375\t,       0.5\t,   0.65625\t,      0.75\t,      0.75\t,   0.65625\t,       0.5\t,  0.359375\t,\n   0.40625\t,  0.578125\t,      0.75\t,     0.875\t,     0.875\t,      0.75\t,  0.578125\t,   0.40625\t,\n   0.40625\t,  0.578125\t,      0.75\t,     0.875\t,     0.875\t,      0.75\t,  0.578125\t,   0.40625\t,\n  0.359375\t,       0.5\t,   0.65625\t,      0.75\t,      0.75\t,   0.65625\t,       0.5\t,  0.359375\t,\n   0.28125\t,     0.375\t,       0.5\t,  0.578125\t,  0.578125\t,       0.5\t,     0.375\t,   0.28125\t,\n    0.1875\t,   0.28125\t,  0.359375\t,   0.40625\t,   0.40625\t,  0.359375\t,   0.28125\t,    0.1875\t,\n\n===========\nmove:3\n     0.125\t,  0.199219\t,  0.263672\t,  0.285156\t,  0.285156\t,  0.263672\t,  0.199219\t,     0.125\t,\n  0.199219\t,  0.289062\t,  0.394531\t,  0.427734\t,  0.427734\t,  0.394531\t,  0.289062\t,  0.199219\t,\n  0.263672\t,  0.394531\t,  0.535156\t,  0.574219\t,  0.574219\t,  0.535156\t,  0.394531\t,  0.263672\t,\n  0.285156\t,  0.427734\t,  0.574219\t,  0.621094\t,  0.621094\t,  0.574219\t,  0.427734\t,  0.285156\t,\n  0.285156\t,  0.427734\t,  0.574219\t,  0.621094\t,  0.621094\t,  0.574219\t,  0.427734\t,  0.285156\t,\n  0.263672\t,  0.394531\t,  0.535156\t,  0.574219\t,  0.574219\t,  0.535156\t,  0.394531\t,  0.263672\t,\n  0.199219\t,  0.289062\t,  0.394531\t,  0.427734\t,  0.427734\t,  0.394531\t,  0.289062\t,  0.199219\t,\n     0.125\t,  0.199219\t,  0.263672\t,  0.285156\t,  0.285156\t,  0.263672\t,  0.199219\t,     0.125\t,\n\n===========\nmove:4\n 0.0986328\t,   0.15332\t,  0.199463\t,  0.224121\t,  0.224121\t,  0.199463\t,   0.15332\t, 0.0986328\t,\n   0.15332\t,  0.214844\t,  0.287109\t,  0.323486\t,  0.323486\t,  0.287109\t,  0.214844\t,   0.15332\t,\n  0.199463\t,  0.287109\t,  0.383301\t,  0.428711\t,  0.428711\t,  0.383301\t,  0.287109\t,  0.199463\t,\n  0.224121\t,  0.323486\t,  0.428711\t,   0.48291\t,   0.48291\t,  0.428711\t,  0.323486\t,  0.224121\t,\n  0.224121\t,  0.323486\t,  0.428711\t,   0.48291\t,   0.48291\t,  0.428711\t,  0.323486\t,  0.224121\t,\n  0.199463\t,  0.287109\t,  0.383301\t,  0.428711\t,  0.428711\t,  0.383301\t,  0.287109\t,  0.199463\t,\n   0.15332\t,  0.214844\t,  0.287109\t,  0.323486\t,  0.323486\t,  0.287109\t,  0.214844\t,   0.15332\t,\n 0.0986328\t,   0.15332\t,  0.199463\t,  0.224121\t,  0.224121\t,  0.199463\t,   0.15332\t, 0.0986328\t,\n\n===========\nmove:5\n 0.0717773\t,  0.113281\t,  0.149078\t,  0.164246\t,  0.164246\t,  0.149078\t,  0.113281\t, 0.0717773\t,\n  0.113281\t,  0.163208\t,  0.219666\t,  0.241852\t,  0.241852\t,  0.219666\t,  0.163208\t,  0.113281\t,\n  0.149078\t,  0.219666\t,  0.295959\t,  0.323669\t,  0.323669\t,  0.295959\t,  0.219666\t,  0.149078\t,\n  0.164246\t,  0.241852\t,  0.323669\t,  0.355652\t,  0.355652\t,  0.323669\t,  0.241852\t,  0.164246\t,\n  0.164246\t,  0.241852\t,  0.323669\t,  0.355652\t,  0.355652\t,  0.323669\t,  0.241852\t,  0.164246\t,\n  0.149078\t,  0.219666\t,  0.295959\t,  0.323669\t,  0.323669\t,  0.295959\t,  0.219666\t,  0.149078\t,\n  0.113281\t,  0.163208\t,  0.219666\t,  0.241852\t,  0.241852\t,  0.219666\t,  0.163208\t,  0.113281\t,\n 0.0717773\t,  0.113281\t,  0.149078\t,  0.164246\t,  0.164246\t,  0.149078\t,  0.113281\t, 0.0717773\t,\n\n===========\nmove:6\n 0.0549164\t, 0.0858612\t,  0.112309\t,  0.125313\t,  0.125313\t,  0.112309\t, 0.0858612\t, 0.0549164\t,\n 0.0858612\t,  0.121979\t,  0.163284\t,  0.182163\t,  0.182163\t,  0.163284\t,  0.121979\t, 0.0858612\t,\n  0.112309\t,  0.163284\t,  0.218758\t,   0.24263\t,   0.24263\t,  0.218758\t,  0.163284\t,  0.112309\t,\n  0.125313\t,  0.182163\t,   0.24263\t,  0.270287\t,  0.270287\t,   0.24263\t,  0.182163\t,  0.125313\t,\n  0.125313\t,  0.182163\t,   0.24263\t,  0.270287\t,  0.270287\t,   0.24263\t,  0.182163\t,  0.125313\t,\n  0.112309\t,  0.163284\t,  0.218758\t,   0.24263\t,   0.24263\t,  0.218758\t,  0.163284\t,  0.112309\t,\n 0.0858612\t,  0.121979\t,  0.163284\t,  0.182163\t,  0.182163\t,  0.163284\t,  0.121979\t, 0.0858612\t,\n 0.0549164\t, 0.0858612\t,  0.112309\t,  0.125313\t,  0.125313\t,  0.112309\t, 0.0858612\t, 0.0549164\t,\n\n===========\nmove:7\n 0.0408211\t, 0.0641537\t, 0.0842423\t, 0.0933313\t, 0.0933313\t, 0.0842423\t, 0.0641537\t, 0.0408211\t,\n 0.0641537\t, 0.0919857\t,  0.123452\t,  0.136641\t,  0.136641\t,  0.123452\t, 0.0919857\t, 0.0641537\t,\n 0.0842423\t,  0.123452\t,  0.165906\t,  0.182574\t,  0.182574\t,  0.165906\t,  0.123452\t, 0.0842423\t,\n 0.0933313\t,  0.136641\t,  0.182574\t,  0.201709\t,  0.201709\t,  0.182574\t,  0.136641\t, 0.0933313\t,\n 0.0933313\t,  0.136641\t,  0.182574\t,  0.201709\t,  0.201709\t,  0.182574\t,  0.136641\t, 0.0933313\t,\n 0.0842423\t,  0.123452\t,  0.165906\t,  0.182574\t,  0.182574\t,  0.165906\t,  0.123452\t, 0.0842423\t,\n 0.0641537\t, 0.0919857\t,  0.123452\t,  0.136641\t,  0.136641\t,  0.123452\t, 0.0919857\t, 0.0641537\t,\n 0.0408211\t, 0.0641537\t, 0.0842423\t, 0.0933313\t, 0.0933313\t, 0.0842423\t, 0.0641537\t, 0.0408211\t,\n\n===========\nmove:8\n  0.030863\t, 0.0483487\t, 0.0633526\t, 0.0704898\t, 0.0704898\t, 0.0633526\t, 0.0483487\t,  0.030863\t,\n 0.0483487\t, 0.0689764\t, 0.0924149\t,  0.102755\t,  0.102755\t, 0.0924149\t, 0.0689764\t, 0.0483487\t,\n 0.0633526\t, 0.0924149\t,  0.123959\t,  0.137064\t,  0.137064\t,  0.123959\t, 0.0924149\t, 0.0633526\t,\n 0.0704898\t,  0.102755\t,  0.137064\t,  0.152143\t,  0.152143\t,  0.137064\t,  0.102755\t, 0.0704898\t,\n 0.0704898\t,  0.102755\t,  0.137064\t,  0.152143\t,  0.152143\t,  0.137064\t,  0.102755\t, 0.0704898\t,\n 0.0633526\t, 0.0924149\t,  0.123959\t,  0.137064\t,  0.137064\t,  0.123959\t, 0.0924149\t, 0.0633526\t,\n 0.0483487\t, 0.0689764\t, 0.0924149\t,  0.102755\t,  0.102755\t, 0.0924149\t, 0.0689764\t, 0.0483487\t,\n  0.030863\t, 0.0483487\t, 0.0633526\t, 0.0704898\t, 0.0704898\t, 0.0633526\t, 0.0483487\t,  0.030863\t,\n\n===========\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n^2k)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n^2k)$$\n# Code\n```\nusing int2=pair<int,int>;\nvector<int2> moves={{1,2},{2, 1},{-1,2},{-2, 1},{1,-2},{2, -1},{-1,-2},{-2, -1}};\nclass Solution {\npublic:\n    vector<vector<vector<double>>> dp;\n    double knight(int n, int k, int i, int j){\n        if (i<0 || i>=n || j<0 || j>=n) return 0;\n        if (k==0) return dp[0][i][j]=1;\n        if (dp[k][i][j]!=-1) return dp[k][i][j];\n        double prob=0;\n        for (auto [a,b]: moves){\n            int r=i+a, s=j+b;\n            prob+=1.0/8*knight(n, k-1, r, s);\n        }\n        return dp[k][i][j]=prob;\n    }\n   \n    double knightProbability(int n, int k, int row, int column) {\n        dp.assign(k+1, vector(n, vector<double>(n, -1.0)));\n        return knight(n, k, row, column);\n    }\n};\n```\n# iterative Code\n```\nusing int2=pair<int,int>;\nvector<int2> moves={{1,2},{2, 1},{-1,2},{-2, 1},{1,-2},{2, -1},{-1,-2},{-2, -1}};\nclass Solution {\npublic:\n    vector<vector<double>> dp;\n    \n    double knight_loop(int n, int k, int r, int c) {\n        if (k == 0) return 1;\n        for (int move = 1; move <= k; move++) { \n            vector<vector<double>> new_dp(n, vector<double>(n)); // Initialize a new dp table for each iteration\n            for (int i = 0; i < n; i++) {\n                for (int j = 0; j < n; j++) {\n                    double prob = 0;\n                    for (auto [a, b] : moves) {\n                        int r1 = i + a, c1 = j + b;\n                        if (r1 >= 0 && r1 < n && c1 >= 0 && c1 < n) {\n                            prob += 0.125 * dp[r1][c1];\n                        }\n                    }\n                    new_dp[i][j] = prob;\n                }\n            }\n            dp = new_dp; // Update dp table for the next iteration\n        }\n        return dp[r][c];\n    }\n   \n    double knightProbability(int n, int k, int row, int column) {\n        dp.assign(n, vector<double>(n, 1));\n        return knight_loop(n, k, row, column);\n    }\n};\n```\n\n![DALL\xB7E 2023-07-22 09.12.02 - Near the dog there are big chess knights in a realistic style.png](https://assets.leetcode.com/users/images/d5d0c5c7-4452-408b-9920-aa5d05dd229f_1689988372.6570885.png)\n
['Dynamic Programming', 'Depth-First Search', 'Memoization', 'C++']