Каковы идеи вариаций проблемы с монетой?

Question

Проблема: учитывая набор n монет с уникальными номиналами и значение change, найдите количество способов внесения изменений для change.

Предполагаямы можем использовать деноминацию более одного раза, вот псевдокод, который я придумал

1. NUM-WAYS(denom[], n, change)
2.   dp = [change + 1][n + 1]
3.   for i = 0 to n
4      dp[i][0] = 1
5.   xs = denom.sorted

6.   for i = 1 to change
7.     for j = 1 to n
8.       if xs[j - 1] > i
9.         dp[i][j] = dp[i][j - 1]
10.      else
11.        dp[i][j] = dp[i - xs[j - 1]][j] + dp[i][j - 1]

12.  return dp[change][n]

Приведенный выше алгоритм мне понятен.Однако, если нам разрешено использовать деноминацию только один раз, тогда строка 11 меняется на dp[i - xs[j - 1]][j - 1] + dp[i][j - 1], как если бы нам вообще не разрешалось использовать текущую деноминацию.Я не могу обернуть голову вокруг этого.Вы можете это объяснить?

Вот несколько тестовых прогонов:

Change: 3, denominations: [8, 3, 1, 2]
11111
01111
01222
01233

// use once
Change: 3, denominations: [8, 3, 1, 2]
11111
01111
00111
00122

Change: 4, denominations: [3, 1, 2]
1111
0111
0122
0123
0134

// use once
Change: 4, denominations: [3, 1, 2]
1111
0111
0011
0012
0001

Answer 1

Пусть dp[i][j] обозначает решение [i, j] -ой подзадачи; то есть, dp[i][j] - количество способов внесения изменений на сумму i с использованием монет от j до n.

Проблема смены монет с повторением

• В первом случае предполагается, что была взята одна монета j -ого достоинства. Поскольку нет ограничений на номиналы, j может остаться прежним, поэтому его можно использовать снова для небольших подзадач: dp[i - xs[j - 1]][j].

Проблема смены монет без повторений

Это то же самое, что и описанная выше проблема с дополнительным ограничением, что монета некоторого достоинства может быть взята только один раз.

• В первом случае предполагается, что была взята одна монета j -ого достоинства. Поскольку мы больше не можем использовать деноминацию j, j меняется на j-1: dp[i - xs[j - 1]][j - 1]

Второй случай одинаков в обеих задачах, где j -й номинал игнорируется.