Задача по математике Сколькими способами купюру в 50 рублей можно разменять монетами в 1 и 2 рубля?

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

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

Пусть dp[i] - количество способов разменять купюру в i рублей. Тогда dp[0] = 1 (так как разменять 0 рублей можно единственным образом - не разменять ничего), dp[1] = 1 (разменять 1 рубль можно одним способом - монетой в 1 рубль), dp[2] = 2 (разменять 2 рубля можно двумя способами - двумя монетами в 1 рубль или одной монетой в 2 рубля).

Далее заполним массив dp по формуле: dp[i] = dp[i - 1] + dp[i - 2]. Таким образом, получим количество способов разменять купюру в 50 рублей.

Код на Python:

Ответ: количество способов разменять купюру в 50 рублей монетами в 1 и 2 рубля - 20365011074.