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

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

Для решения этой задачи можно воспользоваться динамическим программированием.

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

Изначально заполним массив dp[] нулями, кроме dp[0], который равен 1 (так как один способ выбрать 0 рублей - не выбирать ни одной монеты).

Далее пройдемся по всем монетам. Для каждой монеты пройдемся по всем рублям от этой монеты до требуемой суммы Y и прибавим к dp[j] количество способов выбрать сумму j-этой монетой.

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

Таким образом, мы можем найти количество способов выбрать Y рублей из данных монет методом динамического программирования.