怪兽存活概率问题

怪兽,存活,概率,问题 · 浏览次数 : 51

小编点评

## 怪兽存活概率问题分析本问题探讨在 K 次打击后，英雄是否能将怪兽砍死的概率。 **分析步骤：** 1. **暴力解法：** - 首先使用递归函数 `process()` 计算怪兽的死亡概率。 - `process()` 依赖 `dp` 数组，其中 `dp[i][j]` 表示在 i 次打击后，怪兽有 j 点血的概率。 - 递归边界条件： - 如果血量 <= 0，表示怪兽死亡。 - 如果已经死了，但还有机会砍死，则概率为所有可砍的概率。 - 循环计算所有可能的血量值，并累加所有概率。 - 最后返回所有可砍的概率之和。 2. **动态规划优化：** - 由于计算效率有限，可以使用动态规划技术优化暴力解法的效率。 - 在第三个循环中，添加一个剪枝条件，如果 (hp - 1 - M) >= 0，则从 dp[times][hp - 1 - M] 处提取结果。 - 同时，在计算 dp[times][hp] 时，减去 dp[times - 1][hp - 1 - M]。 - 这能有效地减少循环次数，提高效率。 3. **结果分析：** - 两种动态规划方法都能够计算出怪兽在不同打击数下的存活概率。 - 暴力解法计算的概率可能略低，但更易于理解和实现。 - 动态规划方法可以显著提高效率，尤其是在计算复杂概率时。 **代码示例：** **暴力解法：** ```python def process(times, hp): if hp <= 0: return 0 if times == 0: return 1 for i in range(1, M + 1): if hp - i >= 0: dp[times][hp - i] += dp[times - 1][hp - i] return dp[times][hp] ``` **动态规划优化：** ```python def dp2(N, M, K): dp = [[0 for _ in range(N + 1) for _ in range(K + 1)] for _ in range(N + 1)] dp[0][0] = 1 for i in range(1, K + 1): dp[i][0] = dp[i - 1][0] for i in range(1, N + 1): dp[i][i] = dp[i - 1][i - 1] for i in range(1, K + 1): for j in range(1, N + 1): if j - 1 - M >= 0: dp[i][j] -= dp[i - 1][j - 1 - M] dp[i][j] += dp[i - 1][j - 1] return dp[K][N] ``` **注意：** 代码仅供参考，可能需要根据具体需求进行调整。

正文

怪兽存活概率问题

作者：Grey

原文地址：

博客园：怪兽存活概率问题

CSDN：怪兽存活概率问题

题目描述

给定3个参数，N，M，K 怪兽有 N 滴血，等着英雄来砍自己，英雄每一次打击，都会让怪兽流失，
怪兽每一次流失的血量在区间[0……M]上等概率的获得一个值，求 K 次打击之后，英雄把怪兽砍死的概率。

主要思路

由题目含义可知：怪兽在经历 K 次打击后所有可能的掉血情况有 (M+1) 的 K 次方种，，即：

long all = (long) Math.pow(M + 1, K)

如果怪兽在 K 次打击后，被砍死的情况有 kill 种，那么

(double) kill / (double) all;

即为怪兽被砍死的概率。

暴力解法

定义递归函数

long process(int times, int M, int hp)

递归含义是：怪兽还剩 hp 点血，每次的伤害在[0……M]范围上，还有 times 次可以砍，返回砍死的情况数。

那么 base case 有如下两种情况

// 情况一：已经没有被砍的次数了，这个时候，血量如果正好是小于等于0的值， 说明怪兽已经被砍死一次
// 否则怪兽不可被砍死
if (times == 0) {
    return hp <= 0 ? 1 : 0;
}
// 情况二：怪兽已经死了，但是还可以砍
// 此时，所有的砍法都满足条件，所以情况就是(long) Math.pow(M + 1, times)
if (hp <= 0) {
    return (long) Math.pow(M + 1, times);
}

接下来就是普遍情况，由于每次攻击是 [0……M] 中等概率的一个值，则枚举从 0 到 M 任意一个值跑递归函数即可。

long ways = 0;
for (int i = 0; i <= M; i++) {
    ways += process(times - 1, M, hp - i);
}

完整代码如下

public class Code_KillMonster {
    public static double right(int N, int M, int K) {
        if (N < 1 || M < 1 || K < 1) {
            return 0;
        }
        // monster在经历K次打击后所有可能的掉血情况是
        long all = (long) Math.pow(M + 1, K);
        long kill = process(K, M, N);
        return (double) kill / (double) all;
    }

    //怪兽还剩 hp 点血，每次的伤害在[0……M]范围上，还有 times 次可以砍，返回砍死的情况数。
    public static long process(int times, int M, int hp) {
        // 情况一：已经没有被砍的次数了，这个时候，血量如果正好是小于等于0的值， 说明怪兽已经被砍死一次
        // 否则怪兽不可被砍死
        if (times == 0) {
            return hp <= 0 ? 1 : 0;
        }
        // 情况二：怪兽已经死了，但是还可以砍
        // 此时，所有的砍法都满足条件，所以情况就是(long) Math.pow(M + 1, times)
        if (hp <= 0) {
            return (long) Math.pow(M + 1, times);
        }
        long ways = 0;
        for (int i = 0; i <= M; i++) {
            ways += process(times - 1, M, hp - i);
        }
        return ways;
    }
}

动态规划（未做枚举优化）

根据上述暴力递归函数可以得知，递归函数的可变参数有两个，分别是 times 和 hp，且变化范围是固定的，可以定义一个二维数组 dp，表示所有的递归过程解

long[][] dp = new long[K + 1][N + 1];

dp[times][hp] 就表示递归函数long process(int times, int M, int hp)的含义，即：怪兽还剩 hp 点血，每次的伤害在[0……M]范围上，还有 times 次可以砍，砍死的情况数有多少。

根据 base case, 可知

dp[0][0] = 1;

且

dp[times][0] = (long) Math.pow(M + 1, times)

接下来就是普遍位置，根据上述暴力递归函数可知：process(times, M, hp)依赖process(times - 1, M, hp - i)

即dp[times][hp]依赖dp[times-1][hp-i]位置，如下图所示

图中绿色部分的格子依赖黄色部分的格子，

代码如下，

for (int times = 1; times <= K; times++) {
    dp[times][0] = (long) Math.pow(M + 1, times);
    for (int hp = 1; hp <= N; hp++) {
        long ways = 0;
        for (int i = 0; i <= M; i++) {
            if (hp - i >= 0) {
                ways += dp[times - 1][hp - i];
            } else {
                ways += (long) Math.pow(M + 1, times - 1);
            }
        }
        dp[times][hp] = ways;
    }
}

完整代码如下

public class Code_KillMonster {
    public static double dp1(int N, int M, int K) {
        if (N < 1 || M < 1 || K < 1) {
            return 0;
        }
        long all = (long) Math.pow(M + 1, K);
        long[][] dp = new long[K + 1][N + 1];
        dp[0][0] = 1;
        for (int times = 1; times <= K; times++) {
            dp[times][0] = (long) Math.pow(M + 1, times);
            for (int hp = 1; hp <= N; hp++) {
                long ways = 0;
                for (int i = 0; i <= M; i++) {
                    if (hp - i >= 0) {
                        ways += dp[times - 1][hp - i];
                    } else {
                        ways += (long) Math.pow(M + 1, times - 1);
                    }
                }
                dp[times][hp] = ways;
            }
        }
        long kill = dp[K][N];
        return (double) ((double) kill / (double) all);
    }
}

动态规划（枚举优化）

上述动态规划解法中的第三个循环可以优化，再一次看下依赖关系图

当我们得到绿色格子，即dp[times][hp]位置的值以后，如果要求dp[times+1][hp]位置的时候，即如下 target 位置

可以考虑 G 和 H 两个位置

因为 G 位置求的时候，紫色部分格子已经求过了，补上一个 H 位置，就可以把 target 求出来，省略了枚举行为。

完整代码如下

public class Code_KillMonster {
    public static double dp2(int N, int M, int K) {
        if (N < 1 || M < 1 || K < 1) {
            return 0;
        }
        long all = (long) Math.pow(M + 1, K);
        long[][] dp = new long[K + 1][N + 1];
        dp[0][0] = 1;
        for (int times = 1; times <= K; times++) {
            dp[times][0] = (long) Math.pow(M + 1, times);
            for (int hp = 1; hp <= N; hp++) {
                dp[times][hp] = dp[times][hp - 1] + dp[times - 1][hp];
                if (hp - 1 - M >= 0) {
                    dp[times][hp] -= dp[times - 1][hp - 1 - M];
                } else {
                    dp[times][hp] -= Math.pow(M + 1, times - 1);
                }
            }
        }
        long kill = dp[K][N];
        return (double) ((double) kill / (double) all);
    }
}

算法和数据结构笔记