java - 使用动态编程解决问题

Question

在采访中有人问我以下问题。

给定一排房屋，每个房屋都有能量和硬币。
在能量变为负数的情况下可以收集的最大硬币数是多少。
从一所房屋到另一所房屋的能量是1，不能跳过房屋。

例如
例如，EnergyArray = {1、5、3、3、1}和CoinsArray = {3、23、9、2、2}，初始能量为1，则输出应为32，从房屋1中取1能量加上当前能量，因此总能量= 2并前往第二个房子（energy-1 = 1）取硬币，所以硬币= 23，前往第二个房子（energy-1 = 0），取硬币，因此总计32。

同样，对于energyArray = {2，1，1}和coinArray = {11，5，7}且初始能量= 0，输出应为12。

我写的程序就像

public class HouseEnergyCoin {
    /*static int[] energyA = {1,5,3,3,1};
    static int[] coins = {3,23,9,2,2};
    static int initialEnergy = 1;*/
    static int[] energyA = {2,1,1};
    static int[] coins = {11,5,7};
    static int initialEnergy = 0;


    public static void main(String[] args) {

        int energySum = initialEnergy;
        for (int i=0; i< energyA.length;i++){
            energySum+=energyA[i];
        }
        int[][] mem = new int[coins.length+1][energySum];
        System.out.println(maxCoins(initialEnergy, 1, mem));
    }



    static int maxCoins(int energy, int index, int[][] mem) {
        if (energy < 0 || index > coins.length) {
            return 0;
        }
        if (mem[index][energy] != 0){
            return mem[index][energy];
        }
        else {
            int result = max(maxCoins(energy+energyA[index-1]-1,index+1, mem),
                    coins[index-1]+maxCoins(energy-1, index+1, mem));
            mem[index][energy] = result;
            return result;
        }
    }


    static int max(int a, int b) { return (a > b)? a : b; }
}

哪种方法在某些情况下有效，而在某些情况下正在超时，有人可以帮助我提供更好的解决方案吗？

Answer 1

一些提示可能会帮助您：


所需能量的上限是energyA.length，因此int[][] mem = new int[coins.length+1][energyA.length];足够。
如果是coins = [0, 0, 0, 0, 0, 0 .... 0]，您的解决方案将是O(2 ^ coins.lenght)。您需要一种更好的机制来确定您是否在mem中有某种解决方案。
You can turn recursive "top-down" solution to a for loop with "bottom-up" approach。
万一energy > coins.lenght - index，您可以贪婪地取硬币而无需消耗能量。


我的解决方案memory: O(N)，time: O(N^2)：

int UNREACHABLE = -1;

Arrays.fill(sum, UNREACHABLE);
sum[Math.min(initialEnergy + energyA[0], coins.length)] = 0;
sum[Math.min(initialEnergy, coins.length)] = coins[0];

for (int i = 1; i < coins.length; i++) {
    Arrays.fill(newSum, UNREACHABLE);

    for (int energy = 1; energy < coins.length; energy++) {
        if (sum[energy] == UNREACHABLE) {
            continue;
        }

        int newCoins = sum[energy] + coins[i];
        newSum[energy - 1] = Math.max(newCoins, newSum[energy - 1]);

        int newEnergy = Math.min(energy - 1 + energyA[i], coins.length);
        newSum[newEnergy] = Math.max(sum[energy], newSum[newEnergy]);
    }

    int[] temp = sum;
    sum = newSum;
    newSum = temp;
}

int result = Collections.max(Arrays.asList(sum));;
System.out.println(result);