作者：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!");
}
}
}
}
本文來自部落格園，作者：Grey Zeng，轉載請註明原文連結：https://www.cnblogs.com/greyzeng/p/16777406.html