d[x][k] — сколькими способами можно представить x, используя монеты типа не более k. Переход — либо увеличиваем количество типов, либо берём монетку самого большого типа, который можем.

Почему так — попробуем написать перебор и прикрутить к нему запоминание (получим динамику). Пусть как-то набрали. Для определённости (порядок монет неважен) отсортируем их по возрастанию номинала. Заметим, что на очередном шаге перебора нам важно знать лишь остаток суммы и монеты какого минимального номинала мы можем брать.