[dynamic programming] leetcode 688 Knight Probability in Che

发布时间：2020-12-14 05:09:39 所属栏目：大数据来源：网络整理

导读：problem:?https://leetcode.com/problems/knight-probability-in-chessboard/ ? ? ? ? ?This is an easy problem using dfs. class Solution { public : vector int dx{ 1 , 2 , 1 ,- 1 ,- 2 ,- 1 }; vector int dy{ 2 , 2 }; vector vectorvector double dp

problem:?https://leetcode.com/problems/knight-probability-in-chessboard/

? ? ? ? ?This is an easy problem using dfs.

class Solution {
public:
    vector<int> dx{1,2,1,-1,-2,-1};
    vector<int> dy{2,2};
    vector<vector<vector<double>>> dp;
    double knightProbability(int N,int K,int r,int c) {
        double res = 0.0;
        if(K == 0) return 1.0;
        if(dp.empty())
        {
            dp.resize(K + 1,vector<vector<double>>(N,vector<double>(N,-1)));
        }
        if(dp[K][r][c] != -1) return dp[K][r][c];
        for(int k = 0;k < 8 ;k++)
        {
            int x = r + dx[k];
            int y = c + dy[k];
            if(x >= 0 && x < N && y >= 0 && y < N)
            {
                res += knightProbability(N,K - 1,x,y) * 0.125;
            }
        }
        return dp[K][r][c] = res;
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!