Преобразовать неэффективную функцию рекурсивного изменения монет в итерацию

У меня есть неэффективная функция рекурсивного изменения монет, которая определяет количество комбинаций монет для заданной суммы. Я хотел бы преобразовать его в более эффективную итеративную функцию, если это возможно.

Одна из проблем заключается в том, что я использую обратную трассировку, чтобы опробовать разные монеты в массиве под названием деноминации. Я также использую запоминание, но это не ускоряет вещи, когда сумма велика.

Вот мой код:

unsigned long long CalculateCombinations(std::vector<double> &denominations, std::vector<double> change,
double amount, unsigned int index)
{
double current = 0.0;
unsigned long long combinations = 0;

if (amount == 0.0)
{
if (change.size() % 2 == 0)
{
combinations = Calculate(change);
}
return combinations;
}

// If amount is less than 0 then no solution exists
if (amount < 0.0)
return 0;

// If there are no coins and index is greater than 0, then no solution exist
if (index >= denominations.size())
return 0;

std::string str = std::to_string(amount) + "-" + std::to_string(index) + "-" + std::to_string(change.size());

auto it = Memo.find(str);

if (it != Memo.end())
{
return it->second;
}

while (current <= amount)
{
double remainder = amount - current;
combinations += CalculateCombinations(denominations, change, remainder, index + 1);
current += denominations[index];
change.push_back(denominations[index]);
}

Memo[str] = combinations;
return combinations;
}

Есть идеи, как это можно сделать? Я знаю, что есть решения DP для решения проблемы смены монет, но мое не поддается легко. Я могу получить половину копейки.

* Обновление: я изменил функцию на итеративную и увеличил ее в 2 раза, чтобы использовать целые числа, но это не имело существенного значения.

Вот мой новый код:

unsigned long long CalculateCombinations(std::vector<int> &denominations, std::vector<int> change, int amount, unsigned int index)
{
unsigned long long combinations = 0;

if (amount <= 0)
return combinations;

std::stack<Param> mystack;
mystack.push({ change, amount, index });

while (!mystack.empty())
{
int current = 0;
std::vector<int> current_coins = mystack.top().Coins;
int current_amount = mystack.top().Amount;
unsigned int current_index = mystack.top().Index;
mystack.pop();

if (current_amount == 0)
{
if (current_coins.size() % 2 == 0)
{
combinations += Calculate(std::move(current_coins));
}
}
else
{
std::string str = std::to_string(current_amount) + "-" + std::to_string(current_index);
if (Memo.find(str) == Memo.end())
{
// If amount is less than 0 then no solution exists
if (current_amount >= 0 && current_index < denominations.size())
{
while (current <= current_amount)
{
int remainder = current_amount - current;
mystack.push({ current_coins, remainder, current_index + 1 });
current += denominations[current_index];
current_coins.push_back(denominations[current_index]);
}
}
else
{
Memo.insert(str);
}
}
}
}

return combinations;
}

Напоминание определяется как std :: unordered_set.

Может ли это быть решено DP? Проблема в том, что меня не интересуют все комбинации — только комбинации, которые даже по размеру.