Простое динамическое программирование рекурсивной формулы (смена монет uva 147)

Question

Проблема в обмене монет - "сколько способов вы можете обменять на 3,5,10 доллара, если у вас есть 5с, 10с......

" http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=83

проблема решена много раз на различных блогах (решение здесь)

В dp сложнее всего понять связь между подзадачами и получить формулу (оптимальная подструктура)

Я даю только фактический цикл for, который хранит пути в 2d таблице, например, решение:

for (int i = 2; i <= NCHANGES; ++i){
for (int m = 1; m <= MAX_AMOUNT; ++m){
  if (m >= coins[i])
    n[i][m] = n[i-1][m] + n[i][m - coins[i]];
  else
    n[i][m] = n[i-1][m];
}

}

=================================

Фактически важный код:

  if (m >= coins[i])
        n[i][m] = n[i-1][m] + n[i][m - coins[i]];
      else
        n[i][m] = n[i-1][m];

Мое мышление

например: (еще случай)

• У меня есть 5 центов и 1 монета: 5с. есть только 1 способ: 5c = 1 * 5c (сохранить n[5][coin(5)])

• У меня есть 5c и 2 монеты для использования: 5c и 10c я не могу использовать ОБА 5C и 10c => я возвращаюсь к 1 СПОСОБУ этого (сохраните 1 в таблице для n[5][coin(5,10)]) для этого случая

вот почему n[i][m] = n[i-1][m]

Можете ли вы объяснить первый случай? n[i][m] = n[i-1][m] + n [i] [m - монеты [i]]?

Answer 1

Хорошо, я нашел это на веб-сайте - та же проблема.

Периодичность смены монеты: a[i][j] = a[i-1][j] (d[i] > j) (если монету нельзя использовать, не используйте ее)

a [i] [j] = a [i-1] [j] + a [i] [jd [i]] (d [i]<= j) (Если монета может быть использована: не используйте ИЛИ используй это)