打怪兽问题
作者：Grey
原文地址：
题目描述
题目链接: 牛客-打怪兽
开始时你的能力是0，你的目标是从0号怪兽开始，通过所有的怪兽。
如果你当前的能力，小于i号怪兽的能力，你必须付出money[i]的钱，贿赂这个怪兽，然后怪兽就会加入你，他的能力直接累加到你的能力上；
如果你当前的能力，大于等于 i 号怪兽的能力，你可以选择直接通过，你的能力并不会下降，你也可以选择贿赂这个怪兽，然后怪兽就会加入你，他的能力直接累加到你的能力上。
返回通过所有的怪兽，需要花的最小钱数。
主要思路
本题要根据数据量不同使用不同的动态规划解法
情况1：如果怪兽数量不大和血量都不大的情况，定义如下递归函数
long p(int[] hp, int[] money, int i, int j) 递归含义是：当前血量是 j，从第 i 号怪兽开始，到最后通过所有怪兽的最少钱数是多少？
代码和注释说明如下
public static long p(int[] hp, int[] money, int i, int j) { // i 已经到最后了，不需要继续花钱打怪兽 if (i == hp.length) { return 0; } // i号怪兽选择贿赂 long p = money[i] + p(hp, money, i + 1, j + hp[i]); // 不选贿赂i号怪兽，这时候是有条件的，就是当前血量 j 需要大于当前怪兽值 if (j >= hp[i]) { return Math.min(p, p(hp, money, i + 1, j)); } return p; } 通过上述递归函数，可以转换成动态规划，利用一个二维数组即可，代码如下
public static long func1Dp(int[] hp, int[] money) { int sum = 0; for (int a : hp) { sum += a; } long[][] dp = new long[hp.length + 1][sum + 1]; for (int i = hp.length - 1; i >= 0; i--) { for (int j = sum - hp[i]; j >= 0; j--) { dp[i][j] = money[i] + dp[i + 1][j + hp[i]]; if (j >= hp[i]) { dp[i][j] = Math.min(dp[i][j], dp[i + 1][j]); } } } return dp[0][0]; } 这个二维数组的规模就是上述递归函数 i 和 j 的变化范围相乘，其中 i 的变化范围是[0……怪兽数量之和]，j 的变化范围是[0……血量和]。所以适用于怪兽数量和血量都不大的场景。
情况2：如果怪兽能力比较大，但是钱数不大情况，我们需要调整递归函数，定义如下递归函数
long p2(int[] hp, int[] money, int index, int m) 递归含义是：从 0……index 号怪兽，花的钱，必须严格等于 m 的情况下，如果通过不了，返回-1；如果可以通过，返回能通过情况下的最大能力值。
递归方法实现如下
public static long p2(int[] hp, int[] money, int index, int m) { // 从右往左填，base case if (index == -1) { return m == 0 ? 0L : -1L; } // 贿赂当前怪兽 long p1 = p2(hp, money, index - 1, m); long ans = -1; if (p1 != -1 && p1 >= hp[index]) { // 贿赂是有效的，或者贿赂结果可以支持下一次的决策 ans = p1; } // 不贿赂当前怪兽 long p2 = p2(hp, money, index - 1, m - money[index]); if (p2 != -1) { // 可以走到最后，与贿赂得到的能力值pk下。 ans = Math.max(ans, p2 + hp[index]); } return ans; } 同理，这个递归也可以改成动态规划，也是利用一个二维数组，
public static long func4(int[] d, int[] p) { int sum = 0; for (int num : p) { sum += num; } // dp[i][j]含义： // 能经过0～i的怪兽，且花钱为j（花钱的严格等于j）时的武力值最大是多少？ // 如果dp[i][j]==-1，表示经过0～i的怪兽，花钱为j是无法通过的，或者之前的钱怎么组合也得不到正好为j的钱数 int[][] dp = new int[d.length][sum + 1]; for (int i = 0; i < dp.length; i++) { for (int j = 0; j <= sum; j++) { dp[i][j] = -1; } } // 经过0～i的怪兽，花钱数一定为p[0]，达到武力值d[0]的地步。其他第0行的状态一律是无效的 dp[0][p[0]] = d[0]; for (int i = 1; i < d.length; i++) { for (int j = 0; j <= sum; j++) { // 可能性一，为当前怪兽花钱 // 存在条件： // j - p[i]要不越界，并且在钱数为j - p[i]时，要能通过0～i-1的怪兽，并且钱数组合是有效的。 if (j >= p[i] && dp[i - 1][j - p[i]] != -1) { dp[i][j] = dp[i - 1][j - p[i]] + d[i]; } // 可能性二，不为当前怪兽花钱 // 存在条件： // 0~i-1怪兽在花钱为j的情况下，能保证通过当前i位置的怪兽 if (dp[i - 1][j] >= d[i]) { // 两种可能性中，选武力值最大的 dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]); } } } int ans = 0; // dp表最后一行上，dp[N-1][j]代表： // 能经过0～N-1的怪兽，且花钱为j（花钱的严格等于j）时的武力值最大是多少？ // 那么最后一行上，最左侧的不为-1的列数(j)，就是答案 for (int j = 0; j <= sum; j++) { if (dp[d.length - 1][j] != -1) { ans = j; break; } } return ans; } 可以看到二维数组的 dp 规模是钱数 * 达到的最大能力。适用于怪兽能力比较大，但是钱数不大的情况。
完整代码如下(含对数器)
public class NowCoder_BeatMonster { // i到最后通过所有怪兽的最少钱数是多少？ // 适合怪兽能力不大的情况 public static long func1(int[] hp, int[] money) { return p(hp, money, 0, 0); } public static long p(int[] hp, int[] money, int i, int j) { if (i == hp.length) { return 0; } // 选择贿赂 long p = money[i] + p(hp, money, i + 1, j + hp[i]); // 不选贿赂，有条件 if (j >= hp[i]) { return Math.min(p, p(hp, money, i + 1, j)); } return p; } public static long func1Dp(int[] hp, int[] money) { int sum = 0; for (int a : hp) { sum += a; } long[][] dp = new long[hp.length + 1][sum + 1]; for (int i = hp.length - 1; i >= 0; i--) { for (int j = sum - hp[i]; j >= 0; j--) { dp[i][j] = money[i] + dp[i + 1][j + hp[i]]; if (j >= hp[i]) { dp[i][j] = Math.min(dp[i][j], dp[i + 1][j]); } } } return dp[0][0]; } public static long func2(int[] hp, int[] money) { int sum = 0; for (int a : money) { sum += a; } int N = hp.length; for (int i = 0; i < sum; i++) { if (p2(hp, money, N - 1, i) != -1) { return i; } } return sum; } // 从0....index 怪兽，花的钱，必须严格==m // 如果通过不了，返回-1 // 如果可以通过，返回能通过情况下的最大能力值 public static long p2(int[] hp, int[] money, int index, int m) { if (index == -1) { return m == 0 ? 0L : -1L; } // 贿赂当前怪兽 long p1 = p2(hp, money, index - 1, m); long ans = -1; if (p1 != -1 && p1 >= hp[index]) { ans = p1; } long p2 = p2(hp, money, index - 1, m - money[index]); if (p2 != -1) { ans = Math.max(ans, p2 + hp[index]); } return ans; } public static long func4(int[] d, int[] p) { int sum = 0; for (int num : p) { sum += num; } // dp[i][j]含义： // 能经过0～i的怪兽，且花钱为j（花钱的严格等于j）时的武力值最大是多少？ // 如果dp[i][j]==-1，表示经过0～i的怪兽，花钱为j是无法通过的，或者之前的钱怎么组合也得不到正好为j的钱数 int[][] dp = new int[d.length][sum + 1]; for (int i = 0; i < dp.length; i++) { for (int j = 0; j <= sum; j++) { dp[i][j] = -1; } } // 经过0～i的怪兽，花钱数一定为p[0]，达到武力值d[0]的地步。其他第0行的状态一律是无效的 dp[0][p[0]] = d[0]; for (int i = 1; i < d.length; i++) { for (int j = 0; j <= sum; j++) { // 可能性一，为当前怪兽花钱 // 存在条件： // j - p[i]要不越界，并且在钱数为j - p[i]时，要能通过0～i-1的怪兽，并且钱数组合是有效的。 if (j >= p[i] && dp[i - 1][j - p[i]] != -1) { dp[i][j] = dp[i - 1][j - p[i]] + d[i]; } // 可能性二，不为当前怪兽花钱 // 存在条件： // 0~i-1怪兽在花钱为j的情况下，能保证通过当前i位置的怪兽 if (dp[i - 1][j] >= d[i]) { // 两种可能性中，选武力值最大的 dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]); } } } int ans = 0; // dp表最后一行上，dp[N-1][j]代表： // 能经过0～N-1的怪兽，且花钱为j（花钱的严格等于j）时的武力值最大是多少？ // 那么最后一行上，最左侧的不为-1的列数(j)，就是答案 for (int j = 0; j <= sum; j++) { if (dp[d.length - 1][j] != -1) { ans = j; break; } } return ans; } public static int[][] generateTwoRandomArray(int len, int value) { int size = (int) (Math.random() * len) + 1; int[][] arrs = new int[2][size]; for (int i = 0; i < size; i++) { arrs[0][i] = (int) (Math.random() * value) + 1; arrs[1][i] = (int) (Math.random() * value) + 1; } return arrs; } public static void main(String[] args) { int len = 12; int value = 20; int testTimes = 10000; for (int i = 0; i < testTimes; i++) { int[][] arrs = generateTwoRandomArray(len, value); int[] d = arrs[0]; int[] p = arrs[1]; long ans1 = func1(d, p); long ans4 = func1Dp(d, p); long ans2 = func2(d, p); long ans3 = func4(d, p); if (ans1 != ans2 || ans2 != ans3 || ans1 != ans4) { System.out.println("oops!"); } } } } 
