I just want to prove it can work, pure DP, no recursion, no HashMap


  • 0

    Idea is simple, base on the worst case assumption, create a 6 dimension DP array storing all the items counted. Then iterate from 0 to target.

    Performance is not good, which is beyond my expectation. I know the constant of the time complexity is big C * O(N), but it should still be within O(n) range.

    class Solution {
        public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
            if (needs == null || price == null || special == null || needs.size() == 0 || special.size() == 0 || price.size() == 0) return 0;
            int[] dim = new int[6];
            int N = needs.size(); // N items
            
            List<Integer> prices = new ArrayList<>();
            for (int i = 0; i < 6; i++) {
                if (i < price.size()) prices.add(price.get(i));
                else prices.add(0);
            }
            
            for (int i = 0; i < N; i++) dim[i] = needs.get(i);
            int[][][][][][] dp = new int[dim[0]+1][dim[1]+1][dim[2]+1][dim[3]+1][dim[4]+1][dim[5]+1];
            int[] left = new int[6];
            int[] discount = new int[6];
            int[] tmp = new int[6];
            
            for (int i = 0; i <= dim[0]; i++) {
                for (int j = 0; j <= dim[1]; j++) {
                    for (int k = 0; k <= dim[2]; k++) {
                        for (int l = 0; l <= dim[3]; l++) {
                            for (int m = 0; m <= dim[4]; m++) {
                                for (int n = 0; n <= dim[5]; n++) {
                                    left[0] = i; left[1] = j; left[2] = k; left[3] = l; left[4] = m; left[5] = n;
                                    dp[i][j][k][l][m][n] = i * prices.get(0) + j * prices.get(1) + k * prices.get(2) + l * prices.get(3) 
                                        + m * prices.get(4) + n * prices.get(5);
                                    for (int ii = 0; ii < special.size(); ii++) {
                                        cal(left, discount, tmp, special.get(ii), dp);
                                    }
                                 }
                             }
                        }
                    }
                }
            }
            
            return dp[dim[0]][dim[1]][dim[2]][dim[3]][dim[4]][dim[5]];
        }
        
        private void cal(int[] s, int[] discount, int[] left, List<Integer> special, int[][][][][][] dp) {
            for (int i = 0; i < left.length; i++) left[i] = s[i];
            int N = special.size() - 1;
            int price = special.get(N);
            for (int i = 0; i < N; i++) discount[i] = special.get(i);
            int sum = 0;
            while (true) {
                for (int i = 0; i < N; i++) {
                    left[i] -= discount[i];
                    if (left[i] < 0) return;
                }
                sum += price;
                dp[s[0]][s[1]][s[2]][s[3]][s[4]][s[5]] = Math.min(dp[s[0]][s[1]][s[2]][s[3]][s[4]][s[5]], sum + dp[left[0]][left[1]][left[2]][left[3]][left[4]][left[5]]);
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.