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

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

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]]);
}
}
}
``````

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