Задача на комбинаторику Имеется X монет достоинствами N1, N2, N3, ..Nm рублей. Мальчик хочет узнать K - количество способов выбрать из этих монет Y рублей. Монеты одинакового достоинства считаются одинаковыми.

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи можно воспользоваться динамическим программированием. Создадим двумерный массив dp, где dp[i][j] будет обозначать количество способов выбрать j рублей из первых i монет.

Инициализируем dp[0][0] = 1, так как есть один способ выбрать 0 рублей из 0 монет (ничего не выбирать). Далее заполним массив следующим образом:

dp[i][j] = dp[i-1][j] + dp[i][j-coin[i]], если j >= coin[i]
dp[i][j] = dp[i-1][j], если j < coin[i]

Где coin[i] - это значение i-ой монеты.

После заполнения массива dp нужно вернуть значение dp[X][Y]. Это и будет искомое количество способов выбрать Y рублей из X монет.