У меня есть задача найти несколько способов получить сумму заданного числа из массива, содержащего монеты.Например:
монеты: {2,3,5,7}
сумма: 8
всего способов: 6 -> (2 + 2 + 2 + 2), (2 + 3 +3), (3 + 2 + 3), (3 + 3 + 2), (3 + 5) и (5 + 3).
У меня есть решение, которое работает с использованием псевдокода dp:
build an array ar of size "sum"
ar[0]=1
for i = 1 to sum do:
ar[i]=ar[i-2]+ar[i-3]+ar[i-5]+ar[i-7]
return ar[sum]
Как уже упоминалось, этот код работает нормально, но платформа, на которой я работаю, может иметь сумму до 10 * 1010.* 19 , и, как и ожидалось, это дает мне тайм-аут.Есть ли другой способ решить эту проблему?Я даже пытался уменьшить размер массива, когда он выходит за пределы размера i-largest value in coins.Но это также хорошо.