动态规划：砍死怪兽的概率

1、题目

给定3个参数，$n$，$m$，$k$

表示怪兽有 $n$ 滴血，等着英雄来砍自己

英雄每一次打击，都会让怪兽流失 [0 ~ $m$] 的血量

到底流失多少？每一次在 [0 ~ $m$] 上等概率的获得一个值

求 $k$ 次打击之后，英雄把怪兽砍死的概率。

2、思路

本题为字节跳动北美原题。

样本对应模型，因为 $n$ 是样本，怪兽0~n滴血；$k$ 是样本，可以砍 0~k 刀，二维的，因为 $m$ 不变。

英雄每次打击都有 $(m+1)$ 种可能，所以每次打击都是 $(m+1)$ 次展开，所以总共的可能性是 $(m+1{)}^k$。

枚举每种情况下把怪兽砍死的点数，点数之后 / $(m+1{)}^k$ 就是经过 $k$ 次打击后把怪兽砍死的概率。

注意：即便在 $k$ 次之前砍死了也要继续砍（鞭尸），不剪枝。

• 暴力递归版本

public class KillMonster {
    public static double right(int n, int m, int k) {
        if (n < 1 || m < 1 || k < 1) return 0;
        
        long all = (long)Math.pow(m + 1, k); //总的情况数
        long kill = process(k, m, n); //砍死的情况数
        return (double)((double)kill / (double)all);
    }
    
    // 怪兽还剩 hp 点血
    // 每次伤害在 0~m 范围上
    // 还有 times 次可以打击
    // 返回砍死的情况数
    public static long process(int times, int m, int hp) {
		if (times == 0) {
			return hp <= 0 ? 1 : 0;
		}
        
		if (hp <= 0) { //血量小于0的时候，获得的生成点就是 (m + 1) ^ (还剩的打击次数)
			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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

• 动态规划版本

由递推推导 dp 表的时候，如果发现等规模的 dp 表不好构建时（比如出现负数的情况），就总结出一些剪枝的策略进行补进递归中，比如递归中的 hp <= 0 的判断。

//递归函数中可变参数hp（范围0~n）和times（0~k)，所以二维表
public class KillMonster {
    public static double right(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 int[k + 1][n + 1];
        //递归函数中 times 依赖于 times -1，
        dp[0][0] = 1; //第0行的第0列位置为1，其他位置都是0
        for (int times = 1; times <= k; times++) {
            dp[times][0] = (long)Math.pow(m + 1, times); //填0列的值
            for (int hp = 1; hp <= n; hp++) {
                long ways = 0;
                for (int i = 0; i <= m; i++) { //枚举行为
                    //假设还剩3次可以打击，但是此时怪兽血量已经<=0，依然继续打击，每次打击依然是(m+1) 次展开，那么还有 (m+1)^3 个生存点
                    // hp - i可能小于0，所以在前面进行判断
                    //ways += dp[times - 1][hp - i];
                    if (hp - i >= 0) {
                        ways += dp[times - 1][hp - i];
                    } else { //血量<0
                        ways += (long) Math.pow(m + 1, times - 1);
                    }
                }
                dp[times][hp] = ways;
            }
        }
        long kill = dp[k][n]; //砍死的情况数
        return (double)((double) kill / (double) all);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

可见确定二维表的值的时有个枚举行为，观察临近位置（观察动态规划中的枚举行为）。

假设 dp[5][10] 表示的是还有 5 次打击，怪兽还剩 10 点血，而每次打击血量流失范围为 0~3，那么 dp[5][10] 依赖于 dp[4][10]、dp[4][9]、dp[4][8]、dp[4][7] （即dp[4][10...7]），而 dp[5][11] 依赖于 dp[4][11]、dp[4][10]、dp[4][9]、dp[4][8]，

那么 dp[5][11] = dp[5][10] + dp[4][11] - dp[4][7] （dp[4][11...8]）。可见依赖的变化范围是和 $m$ 相关的。

抽象可得，那么知道了 dp[i][j - 1] 的值如何得到 dp[i][j] 的值呢？

dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1 - m]

所以可以进行优化。

• 动态规划优化版本（斜率优化）

public class KillMonster {
    public static double right(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 int[k + 1][n + 1];
        //递归函数中 times 依赖于 times -1，
        dp[0][0] = 1; //第0行的第0列位置为1，其他位置都是0
        for (int times = 1; times <= k; times++) {
            dp[times][0] = (long)Math.pow(m + 1, times); //填0列的值
            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[3][3], m = 5
                    //那么dp[3][3] = dp[2][3...-2]
                    //dp[3][4] = dp[2][4...-1]
                    //则dp[3][4] = dp[3][3] + dp[2][4] - dp[2][-2], 而 dp[2][-2] 的情况是由公式决定的
                    dp[times][hp] -= Math.pow(m + 1, times - 1);
                }
            }
        }
        long kill = dp[k][n]; //砍死的情况数
        return (double)((double) kill / (double) all);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27