Tushar's Birthday Parth InterviewBit hritikkumar.java

public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public int solve(final List<Integer> friendCapacity, final List<Integer> dishCapacity, final List<Integer> dishCost) {
        // get maximum cost of all friend
        int maxFriendCost = Collections.max(friendCapacity);
        // generate dp table for that maximum friend cost
        List<List<Integer>> dpTable = getMinCost(dishCapacity, dishCost, maxFriendCost);
        
        // use the dp_table for each friends' cost 
        int result = 0;
        // sum them
        for(int capacity: friendCapacity) {
            result += dpTable.get(dpTable.size() - 1).get(capacity);
        }
        return result;
    }
    private List<List<Integer>> getMinCost(List<Integer> dishCapacity, List<Integer> dishCost, int cost) {
        List<List<Integer>> dpTable = get2DArrayList(dishCapacity.size() + 1, cost + 1);
        // for 0 elements minimum dish cost for friend's cost will be Infinity so integer max value
        for(int i=1;i<dpTable.get(0).size();i++) {
            dpTable.get(0).set(i, Integer.MAX_VALUE);
        } 
        // here we are using simple unbounded knapsack dp for MINIMUM NOT MAXIMUM
        for(int i=1;i<dpTable.size();i++) {
            for(int j=1;j<dpTable.get(0).size();j++) {
                if(dishCapacity.get(i-1) <= j) {
                    int val = dpTable.get(i-1).get(j);
                    int val2 = dpTable.get(i).get(j-dishCapacity.get(i-1));
                    // val2 can be Integer.max value so having a condition for that
                    if(val2 != Integer.MAX_VALUE) {
                        val2 += dishCost.get(i-1);
                    }
                    val = Math.min(val, val2);
                    dpTable.get(i).set(j, val);
                } else {
                    dpTable.get(i).set(j, dpTable.get(i-1).get(j));
                }
            }
        }
        return dpTable;
    }
    
    // Util function for 2d array list in java
    private List<List<Integer>> get2DArrayList(int n, int m) {
        List<List<Integer>> result = new ArrayList<>();
        for(int i=0;i<n;i++) {
            result.add(new ArrayList<>());
            for(int j = 0; j<m;j++) {
                result.get(i).add(0);
            }
        }
        return result;
    }
}