Алгоритм смены монет и псевдокод: требуется уточнение

Question

Я пытаюсь понять решение проблемы с изменением монет, но у меня есть некоторые трудности.

В the Algorithmist, есть псевдокод решение для динамического решения программирования, как показано ниже:

n = goal number 
S = [S1, S2, S3 ... Sm] 

function sequence(n, m) 
    //initialize base cases 

    for i = 0 to n 
    for j = 0 to m 
     table[i][j] = table[i-S[j]][j] + table[i][j-1] 

Это довольно стандартный O(n^2) алгоритм, который позволяет избежать повторного вычисления тот же ответ несколько раз, используя массив 2-D ,

Моя проблема заключается в два раза:

1. Как определить базовые случаи и включить их в table[][] в качестве начальных значений
2. Как извлечь из различных последовательностей из таблицы

Что касается вопроса 1, то с этим алгоритмом существует три основных случая:

• if n==0, return 1
• if n < 0, return 0
• if n >= 1 && m <= 0, return 0

Как включить их в table[][], я не уверен. Наконец, я не знаю, как извлечь набор решений из массива.

Answer 1

Мы можем реализовать алгоритм динамического программирования, по крайней мере, в двух разных подходах. Один из них - подход сверху вниз с использованием memoization, другой - итеративный подход снизу вверх.

Для начинающих для динамического программирования я всегда рекомендую сначала использовать подход сверху вниз, так как это поможет им понять отношения повторения в динамическом программировании.

Так что для того, чтобы решить эту монету изменяющейся проблемы, вы уже поняли, что говорят отношения рецидивов:

table[i][j] = table[i-S[j]][j] + table[i][j-1] 

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

Так что будет, когда мы попытаемся спуститься по рекурсивному дереву?

Если нам нужно вычислить table[i][j], что означает число подходов для изменения i с использованием монет от типа 0 к j, есть несколько случаев угла, мы должны обращаться:

1) Что делать, если j == 0?

Если j == 0 мы постараемся решить подзапрос table(i,j-1), что является недопустимой подзадачей.Таким образом, один граничное условие:

if(j==0) { 
    if(i==0) table[i][j] = 1; 
    else table[i][j] = 0; 
} 

2) Что делать, если i - S[j] < 0?

Нам также необходимо обработать этот граничный случай, и мы знаем, что в таком состоянии мы не должны пытаться решить эту подзадачу или инициализировать table(i-S[j],j) = 0 для всех этих случаев.

Итак во всем, если мы собираемся реализовать это динамическое программирование от запоминания подхода сверху вниз, мы можем сделать что-то вроде этого:

int f(int i, int j) { 
    if(calc[i][j]) return table[i][j]; 
    calc[i][j] = true; 
    if(j==0) { 
    if(i==0) return table[i][j]=1; 
    else return table[i][j]=0; 
    } 
    if(i>=S[j]) 
    return table[i][j]=table[i-S[j][j]+table[i][j-1]; 
    else 
    return table[i][j]=table[i][j-1]; 
} 

На практике, это также возможно, что мы используем значение из table массивов, чтобы помочь отслеживать, была ли эта подзадача ранее вычислена (например, мы можем инициализировать значение -1, эта подзадача не была рассчитана).

Надеюсь, что ответ ясен. :)