一 求K次打击之后，英雄把怪兽砍死的概率

1.1 描述

给定3个参数，N，M，K

怪兽有N滴血，等着英雄来砍自己

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

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

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

1.2 分析 尝试

第一砍可能让他掉0滴血到m滴血，就是0到m的展开，k次的话就是有（1+m）有k个相乘 math.pow(m+1,k)

1.3 代码

    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) {
            //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.4 改动态规划

base条件是当前times==0 ，hp

hp - i 当 hp 剩余血量为0，但是还有3刀的情况那么hp - i就会越界

推表的时候，又出现小于的表的情况就剪支

1.5 动态规划代码

	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);
	}