Уникальные комбинации чисел, которые складываются до суммы

Question

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

Учитывая номер, найдите все возможные способы, которые вы можете добавить к нему, используя только цифры 1,2,3. Таким образом, для ввода 3 выход будет равен 4, поскольку комбинации будут 1,1,1 и 1,2 и 2,1 и 3. Я знаю об алгоритме изменения монет, но это не дает мне, что перестановка 1,2 и 2,1. Так что я просто закончил реализацию алгоритма замены монет и не смог получить часть перестановки. У кого-нибудь есть идеи?

Answer 1

Это рекурсивная проблема:

взять, например, возможные варианты 5

X X X X X 
1 X X X X 
2 X X X 
3  X X 

Так f(5)=f(4) + f(3) + f(2)

Таким образом, общее решение

f(1)=1 
f(2)=2 
f(3)=4 
f(N)= f(N-1) + f(N-2) + f(N-3) for N > 3 

Answer 2

Чтобы ответить на ваш вопрос о классификации проблемы, мне кажется, что проблема с динамическим программированием. См следующего вопроса взят из stanford.edu

1-мерного DP Пример

◮ Problem: given n, find the number of different ways to write 
n as the sum of 1, 3, 4 
◮ Example: for n = 5, the answer is 6 
5 = 1 + 1 + 1 + 1 + 1 
= 1 + 1 + 3 
= 1 + 3 + 1 
= 3 + 1 + 1 
= 1 + 4 
= 4 + 1 

А вот solution to similar problem