пару месяцев go У меня было домашнее задание, в котором было решение DP. Несмотря на то, что я смог решить ее по-своему (с сортировкой и повторением, которые также получили только половину балла, потому что намного медленнее, чем официально) Я до сих пор не очень хорошо понимаю решение DP. Вопрос был в том, что если у вас есть n магазинов и k товаров, распределите количество товаров поровну между магазинами, чтобы минимизировать ваши затраты.
Так что, если у вас n = 3 магазина и 3 товара, вам нужно выбрать один. пункт из каждого магазина, чтобы минимизировать ваши затраты.
Официальное решение очень простое и короткое, но я просто не понимаю его.
Таблица n-мерная (количество магазинов ). И это код для n = 3
int[][][] table = new int[p + 1][p + 1][p + 1];
for (int i = 0; i < p + 1; ++i) {
for (int j = 0; j < p + 1; ++j) {
for (int l = 0; l < p + 1; ++l) {
if (i == 0 && j == 0 && l == 0) {
table[0][0][0] = 0;
continue;
}
int pi, pj, pl;
if (i == 0) {
pi = Integer.MAX_VALUE;
} else {
pi = table[i - 1][j][l] + prices[0][i+j+l - 1];
}
if (j == 0) {
pj = Integer.MAX_VALUE;
} else {
pj = table[i][j - 1][l] + prices[1][i+j+l - 1];
}
if (l == 0) {
pl = Integer.MAX_VALUE;
} else {
pl = table[i][j][l - 1] + prices[2][i+j+l - 1];
}
table[i][j][l] = min(pl, pj, pi);
}
}
}
return table[p][p][p];
Может кто-нибудь увидеть, как это работает? Я смог придумать много решений DP, я чувствовал, что это похоже на ранец, когда впервые увидел вопрос (но я не мог придумать решение ранцев), но это совсем не похоже на ранец.
Спасибо.