Problem solving using dynamic programming

Question

I was asked in an interview the below question.

Given a row of houses which have energy and coins associated with each one of them. What is the maximum coins that can be collected without energy becoming negative. Energy to travel from one house to another is 1, houses cannot be skipped.

For example example EnergyArray = {1, 5, 3, 3, 1} and CoinsArray = {3, 23, 9, 2, 2} and initial energy is given as 1 then output should be 32, cause take 1 energy from house 1 add with current energy, so total energy = 2 and travel to 2nd house (energy-1 = 1) take coins so coins = 23, travel to next house(energy-1 = 0) take coins so total 32.

Similarly for energyArray = {2, 1, 1} and coinsArray = {11, 5, 7} and initial energy = 0, output should be 12.

The program I wrote is like

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; }
}

which is working for some scenarios and for others it's timing out, can somebody please help me with a better solution ?

Answer 1

Few tips that might help you:

• Upper bound of needed energy is energyA.length, so int[][] mem = new int[coins.length+1][energyA.length]; is enough.
• In case coins = [0, 0, 0, 0, 0, 0 .... 0], your solution would be O(2 ^ coins.lenght). You need a better mechanism to decide if you have some solution in mem.
• You can turn recursive "top-down" solution to a for loop with "bottom-up" approach.
• In case energy > coins.lenght - index, you can just greedily take coins without taking energy.

My solution 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);