C++ DP Solution Explained
Runtime: 8 ms, faster than 86.35% of C++ online submissions for Knight Probability in Chessboard.\nMemory Usage: 6.9 MB, less than 5.54% of C++ online submissio
Runtime: 8 ms, faster than 86.35% of C++ online submissions for Knight Probability in Chessboard.\nMemory Usage: 6.9 MB, less than 5.54% of C++ online submissions for Knight Probability in Chessboard.\n\n```\nHere knight\'s each move has probability 1.0/8.0 = 0.125. Now intially in position start = (r,c) the proabability\nof knight move is 1.0 so, when there is a move from start to new position child (r+x, c+y), the probability of\nnew position will be prob_new_pos += prob_start/ 8.0 and same goes for all other parent and child positions.\nAs there can be multiple way to end up in a position from different positions, we add their probability as\nthose are mutually exclusive events and also from parent to child position we divide parent probability by\n8.0 as those events are dependent or in chain and every move has proability 1/8.  After K steps , we sum up\nall the probability of the chess board positions.\n\nExample: N = 3, K = 2, r= 0, c = 0\n```\n\n\n![image](https://assets.leetcode.com/users/images/1fdc28a2-1430-4be5-8c21-7b422ac450dc_1602412179.1889427.png)\n\n```\nSo, total probability =  0.015625 * 4 = 0.0625\n\n\'Time Complexity = O(N * N * K)\'\n```\n\n\n```\nclass Solution {\npublic:\n    \n    double knightProbability(int N, int K, int r, int c){\n        \n        // no moves so probability 1\n        if(K==0) return 1.0;\n        \n        // parent chess board\n        vector<vector<double>> parentBoard(N,vector<double>(N,0.0));\n        \n        // child chess board\n        vector<vector<double>> childBoard(N,vector<double>(N,0.0));\n        \n        // row and col offset for generating next move or child positions\n        int rowoffset[] = {-2,-2,-1,-1,2,2,1,1};\n        int coloffset[] = {1,-1,2,-2,1,-1,2,-2};\n        \n        int cx,cy;\n        \n        // initial position probability 1\n        parentBoard[r][c] = 1.0;\n        \n        // Run K steps\n        // Each step update the child position probability from parent position \n        // After each step assign child as parent board and create new child board\n        for(int i=0;i<K;i++)\n        {\n            for(int p=0;p<N;p++)\n            {\n                for(int q=0;q<N;q++)\n                { \n                    // calculate child position proabilty once from parent position probability\n                    double moveProb = parentBoard[p][q]/8.0;\n                    \n                    // generate valid child positions\n                    for(int w=0;w<8;w++)\n                    {\n                        cx = p + rowoffset[w];\n                        cy = q + coloffset[w];\n\n                        // update child position probability\n                        if(cx>=0 && cx<N && cy>=0 && cy<N)\n                            childBoard[cx][cy] += moveProb;\n                    }                    \n                }\n            }\n            \n            parentBoard = childBoard;\n            fill(childBoard.begin(),childBoard.end(),vector<double>(N,0.0));\n        }\n        \n\n        \n        double knightProb = 0.0;\n        \n        // Loop through parent board after K steps and sum up all probability\n        for(int p=0;p<N;p++)\n            for(int q=0;q<N;q++)\n                   knightProb+=parentBoard[p][q];\n\n        return knightProb;\n    }\n};\n```
['Dynamic Programming', 'C']