algo-aha

马在K步后留在棋盘上的概率

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

double knightProbability(int N, int K, int r, int c) {
    // 设prob[i][j][k]表示马在第i行j列、已跳k步的概率，
    // prob[i][j][k] = 来自8个位置的概率prob[i-dr][j-dc][k-1]的和
    // 递推式在k维只依赖k-1项，可省掉k维，k仍从左往右遍历
    const vector<array<int, 2>> d = { {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, 
                                        {2, -1}, {1, -2}, {-1, -2}, {-2, -1} };
    vector<vector<double>> prob(N, vector<double>(N, 0));
    prob[r][c] = 1;
    
    // 模拟走步更新概率分布
    for (int k = 1; k <= K; k++) {
        vector<vector<double>> nprob(N, vector<double>(N, 0));
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int m = 0; m < d.size(); m++) {
                    int pi = i - d[m][0], pj = j - d[m][1];
                    if (0 <= pi && pi < N && 0 <= pj && pj < N) {
                        nprob[i][j] += prob[pi][pj] / 8;
                    }
                }
            }
        }
        swap(prob, nprob);
    }
    
    double ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            ans += prob[i][j];
        }
    }
    return ans;
}

马走日拨号器，按N次有多少种不同号码

• https://leetcode.com/problems/knight-dialer
• https://leetcode.com/problems/count-vowels-permutation/

int knightDialer(int N) {
    const int MOD = 1e9 + 7;
    // 各数字可以跳到哪些数字
    vector<vector<int>> jump = {
        {4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9},
        {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}
    };
    // 动态规划，设dp[i][d]表示i个数以数字d结尾的号码数，
    // dp[i][dst] = sum(dp[i-1][src])
    // i只依赖前一项，省掉i这维，ndp[dst] = sum(dp[src])
    vector<long> dp(10, 1);
    for (int i = 1; i < N; i++) { // 跳N-1次
        vector<long> ndp(10, 0);
        for (int d = 0; d < 10; d++) {
            for (int nd : jump[d]) {
                ndp[nd] += dp[d] % MOD;
            }
        }
        swap(ndp, dp);
    }
    
    return accumulate(begin(dp), end(dp), 0L) % MOD;
}

供应A,B两种汤

• https://leetcode.com/problems/soup-servings/

double soupServings(int N) {
    if (N >= 5000) return 1; // tricky：单调递增，N太大时直接返回1
    map<array<int, 2>, double> memo; // A,B剩余 => 概率
    return prob(N, N, memo);
}

double prob(int a, int b, map<array<int, 2>, double> &memo) {
    // 基本的终止情况
    if (a <= 0 && b <= 0) return 0.5;
    if (a <= 0) return 1;
    if (b <= 0) return 0;
    if (memo.count({a, b})) return memo[{a, b}];

    vector<vector<int>> ops = { {100, 0}, {75, 25}, {50, 50}, {25, 75} };
    double ans = 0;
    for (auto &op : ops) {
        ans += 0.25 * prob(a - op[0], b - op[1], memo);
    }        
    memo[{a, b}] = ans;
    return ans;
}

得分在[K,N]间的概率

• https://leetcode.com/problems/new-21-game/

double new21Game(int N, int K, int W) {
    // 题目：<K时不断得[1..W]分，求最后得分在[K..N]间的概率
    if (K == 0 || N - K + 1 >= W) return 1;
    // 设dp[i]表示得分为i的概率，则dp[i]=sum{dp[i-W..i-1]}/W
    // 由于得分>=K就不再得分，dp[K..i-1]=0，dp[i]=sum{dp[i-W..min(K-1,i-1)]}/W
    // 维护一个长<=W的窗口，设Wsum=sum{dp[i-W..min(K-1,i-1)]}
    vector<double> dp(N + 1, 0);
    dp[0] = 1;
    double Wsum = dp[0], ans = 0;
    for (int i = 1; i <= N; i++) {
        dp[i] = Wsum / W;
        // 更新Wsum
        if (i < K) Wsum += dp[i]; // min(K-1,i-1)=i-1，扩展窗口右边界
        else ans += dp[i]; // min(K-1,i-1)=K-1，不用扩展窗口右边界；i>=K，正好可以统计[K..N]间的概率
        if (i-W >= 0) Wsum -= dp[i-W]; // 收缩窗口左边界
    }
    return ans;
}