Решение проблем с использованием Dynami c программирования

Question

Мне задали в интервью следующий вопрос.

Учитывая ряд домов, в которых есть энергия и монеты, связанные с каждым из них. Какое максимальное количество монет может быть собрано без энергии, становящейся отрицательной. Энергия для перемещения из одного дома в другой равна 1, дома не могут быть пропущены.

Например, например, EnergyArray = {1, 5, 3, 3, 1} и CoinsArray = {3, 23, 9, 2, 2}, и начальная энергия дана как 1, тогда выходной сигнал должен быть 32, причина возьмите 1 энергию из дома 1, добавьте к ней текущую энергию, так что полная энергия = 2 и отправьтесь во 2-й дом (энергия-1 = 1), возьмите монеты, чтобы монеты = 23, перейдите к следующему дому (энергия-1 = 0), возьмите монеты, так что всего 32.

Аналогично для energyArray = {2, 1, 1} и coinsArray = {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; }
}

, который работает для некоторых сценариев ios, а для других это время ожидания, может кто-нибудь, пожалуйста, помогите мне с лучшим решением?

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.
• Вы можете превратить рекурсивное «нисходящее» решение в a для l oop с «восходящим» подходом .
• В случае 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);