Задача 13 Сколькими способами можно разменять купюру в 1000

---

Задача 13 
Сколькими способами можно разменять купюру в 1000
сум купюрами по 50, 100 200, 500 сум?
Для решения этой задачи можно использовать метод
динамического программирования.
Пусть dp(i) - количество способов разменять сумму i купюрами 50,
100, 200, 500 сум. Тогда для каждого i мы можем разменять сумму i
либо купюрами 50 сум (dp(i-50)), либо купюрами 100 сум (dp(i-100)),
либо купюрами 200 сум (dp(i-200)), либо купюрами 500 сум (dp(i-500)).
Таким образом, мы можем записать рекуррентное соотношение:
dp(i) = dp(i-50) + dp(i-100) + dp(i-200) + dp(i-500)
Исходное значение dp(0) равно 1, так что мы можем начать
заполнять таблицу, начиная с dp(50) и заканчивая dp(1000).
Искомым ответом будет значение dp(1000).
Код на Python:
dp = [0] * 1000
dp[0] = 1
for i in range(50, 1001):
dp[i] = dp[i-50] + dp[i-100] + dp[i-200] + dp[i-500]
print(dp[1000])
Ответ: 12641060625 способов.