Сколькими способами можно разложить число s на слагаемые ?

[dcghtu]

Сколькими способами можно разложить число s на слагаемые 1,2,5,50,100, используя не более 20 слагаемых?
Порядок следования слагаемых не важен, можно использовать одинаковые слагаемые, т. е., например 4,можно преставлять так 2+2, 1+1+1+1 , 4...Объясните только как это решать?

[demolishka]

Гуглить по запросу "динамическое программирование". Хотя конечно в Вашем конкретном случае можно и формулу вывести, но она будет некрасивой.

[StaticZero]

См. задача о размене монет.

Идеей может быть следующая посылка: в данном разложении каждое слагаемое само может быть разложено на составляющие.

Попробуйте сначала разложить каждую монету из вашей системы $(1, 2, 5, 50, 100)$ на составляющие. Сколькими способами это можно сделать для каждой из них? А по ходу дела вы и поймёте, как это работает.