mzoe666888

V1

2022/04/17阅读:19主题:兰青

花最少的钱通过所有的怪兽

腾讯面试题:打怪兽问题,花最少的钱通过所有怪兽,本文将通过三种方法实现,您将学到如何用暴力递归改动态规划,其次需要根据数据量来分析,实现最优解的动态规划,属于根据数据量猜解法的技巧。

int[] d,d[i]:i号怪兽的能力

int[] p,p[i]:i号怪兽要求的钱

开始时你的能力是0,你的目标是从0号怪兽开始,通过所有的怪兽。

如果你当前的能力,小于i号怪兽的能力,你必须付出p[i]的钱,贿赂这个怪兽,然后怪兽就会加入你,他的能力直接累加到你的能力上;如果你当前的能力,大于等于i号怪兽的能力,你可以选择直接通过,你的能力并不会下降,你也可以选择贿赂这个怪兽,然后怪兽就会加入你,他的能力直接累加到你的能力上。

返回通过所有的怪兽,需要花的最小钱数。

腾讯面试题

一、分析

如果你的能力大于等于怪兽的能力,有两种选择:

  • 第一种:直接通过,也不花钱,能力也不增长
  • 第二种:贿赂怪兽,花钱,能力提升

如果你的能力小于怪兽的能力,只能花钱贿赂怪兽,然后能力值提升

方法一暴力递归,ability:当前你所具有的能力,index:当前来到第index个怪兽的面前,目前你的能力是ability,你来到了index号怪兽的面前,如果要通过后续所有的怪兽,请返回需要花的最少钱数。

方法二动态规划,由暴力递归发现只有两个可变参数(ability,index),准备一张二维dp表,index号怪兽做行,ability能力做列,index的变化范围0~N,ability的变化范围0~sum,所有能力加起来为sum。

方法三动态规划,如果能力范围变化很大,可能导致dp表过大,导致方法执行效率不高,重新定义dp,dp[i][j]含义:能经过0~i的怪兽,且花钱为j(花的钱严格等于j)时的武力值最大是多少?

分析可能性:

  • 可能性一:为当前怪兽花钱
  • 可能性二:不为当前怪兽花钱

总结:如果sum能力值变化范围不大,则方法二就可以,如果sum变化范围很大,则方法三是最优解,这道题属于根据数据量猜解法

二、实现

1、暴力递归(方法一)

public static long func1(int[] d, int[] p) {
    return process(d, p, 00);
}

// 当前你的能力是ability,来到index号怪兽面前,后续通过所有关需要花的最少的钱
public static long process(int[] d, int[] p, int ability, int index) {
    if (index == d.length) { // base case
        return 0;
    }
    if (ability < d[index]) { // 当前的能力小于当前怪兽的能力,没得选,只能花钱贿赂,花了钱能力就增长
        return p[index] + process(d, p, ability + d[index], index + 1);
    } else { // 可以贿赂,也可以不贿赂
        return Math.min(
                p[index] + process(d, p, ability + d[index], index + 1),
                process(d, p, ability, index + 1)
        );
    }
}

2、动态规划(方法二)

public static long func2(int[] d, int[] p) {
    int sum = 0;
    for (int num : d) { // 累加所有能力值
        sum += num;
    }
    // 怪兽范围为0~N+1,能力范围为0~sum+1
    long[][] dp = new long[d.length + 1][sum + 1];
    for (int index = d.length - 1; index >= 0; index--) { // 从下往上推
        for (int ability = 0; ability <= sum; ability++) {
            if (ability + d[index] > sum) {
                continue;
            }
            if (ability < d[index]) { // 当前具备的能力小于当前怪兽的能力,没得选,只能花钱贿赂怪兽,然后能力增长
                dp[index][ability] = p[index] + dp[index + 1][ability + d[index]];
            } else { // 当前具备的能力大于等于当前怪兽的能力:两种选择
                dp[index][ability] = Math.min(p[index] + dp[index + 1][ability + d[index]], dp[index + 1][ability]);
            }
        }
    }
    return dp[0][0];
}

3、动态规划(方法三)

public static long func3(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;
}

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1