Наблюдението е следното:

Имаме монетите { 1, 2, 3 } и трябва да намерим всички начини (комбинации) да получим сумата S = 4. Ако махнем монетата 3, проблемът остава същият - с по-малък брой монети. Да примем, че знаем решението с монетите { 1, 2 } - 3 начина. Как това ни помага, когато добавим 3 към възможните монети? 

При всяко положение намерените начини поне ще се запазят. Добавяйки монети, решението може само да се разшири. Кога се разширява? В два случая:

• Ако монетата е равна на сумата която търсим (напр. при S = 3, { 1, 2, 3 }, с 3 ще имаме още 1 начин да получим 3).
• Ако съществуват вече начини да получим сумата - монетата. (напр. при S = 4, { 1, 2, 3 }, с 3 ще имаме също толкова начини да получим 4 колкото досега + начините да получим 1 (към които ще добавим 3, за да стане сумата 4).

И тука вече можем да си изведем следната рекурентна зависимост:

начините да получим 4 с { 1, 2, 3 } = начините да получим 4 с { 1, 2 } + начините да получим (4 - 3) с { 1, 2, 3 }

По-точно: Combinations(c, S) = Combinations(c - 1, S) + Combinations(c, S - coins[c]), където c е индексът на текущата монета, а S - търсената сума.

С bottom-up подход, много лесно може да си го изведем в таблица (редовете са монетите, колоните са сумите):

    0 1 2 3 4   
1  0 1 1 1 1
2  0 1 2 2 3
3  0 1 2 3 4

Стойностите в клетките отговарят на начините, по които можем да образуваме текущата сума, ползвайки всички монети до момента.

Помислете дали цялата таблица ни е необходима - можем ли да спестим памет? :)