打败怪兽的概率

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

暴力递归

先把能打出伤害点数的可能性全部求出来:
long all = Math.pow(M + 1,K);
因为伤害是 0 - M 所以求所有可能性时是 M + 1
然后递归每种可能出现的伤害.

代码演示

  /**** @param N 怪兽有N滴血，* @param M 英雄每一次打击， 都会让怪兽流失[0~M]的血量* @param K K次打击* @return*/public static double killMonster(int N,int M,int K){if (N < 1 || M < 1 || K < 1) {return 0;}long process = process(N, M, K);long all = (long)Math.pow(M + 1, K);return  (double)process /(double)all;}/*** 递归* @param N 怪兽有N滴血，* @param M 英雄每一次打击， 都会让怪兽流失[0~M]的血量* @param K K次打击* @return*/public static long process(int N,int M,int K){//base caseif (K == 0){return N <= 0 ? 1 : 0;}//如果次数还没用完,怪兽就死了,那么剩下的刀数直接求可能出现的所有可能if (N <= 0){return (long)Math.pow(M + 1,K);}int ans = 0;//递归每种可能打出来的伤害for (int i = 0; i <= M;i++){ans += process(N - i,M,K - 1);}return ans;}

动态规划

对递归进行改写,先确定动态规划表如何设置,找到递归中的变量.
每次剩余的血量和砍的次数,因此二维数组就可以了.
然后改写三步骤:
1.根绝base case 初始化变量
2.递归过程改写
3.返回递归最开始调用的过程

代码演示

   /*** 动态规划* @param N 怪兽有N滴血，* @param M 英雄每一次打击， 都会让怪兽流失[0~M]的血量* @param K K次打击* @return*/public static double hp(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];//base case 初始化dp[0][0] = 1;//i 是可以砍怪兽的次数for (int i = 1; i <= K;i++){//血量为0 后,如果次数还没用完,怪兽就死了,那么剩下的刀数直接求可能出现的所有可能dp[i][0] = (long)Math.pow(M + 1,i);//j 是怪兽的血量for (int j = 1; j <= N;j++){int ans = 0;//每次砍可能掉的血量,for (int hp = 0; hp <= M;hp++){if (j - hp >= 0){ans += dp[i - 1][j - hp];}else{ans +=  (long)Math.pow(M + 1,i - 1);}}dp[i][j] = ans;}}long kill =  dp[K][N];return (double) kill / (double) all;}

动态规划专题

'leetcode688. 骑士在棋盘上的概率

凑零钱.钱币的组合有多少种

最小路径和

最长回文子序列

leetcode1143. 最长公共子序列

leetcode51. N 皇后