打怪兽问题
作者：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!");
}
}
}
}