通过动态规划进行变革的所有解决方案

Question

我正在复习算法课的讲义，我开始思考这个问题：

给定不同类型的硬币具有不同的价值，找到所有硬币配置加起来达到一定的总和，且不重复。

在课堂上，我们解决了求和的所有可能方式的数量以及求和的最少硬币数量的问题。然而，我们从未尝试真正找到解决方案。

我正在考虑用动态规划来解决这个问题。

我附带了递归版本（为了简单起见，我只打印了解决方案）：

void solve(vector<string>& result, string& currSoln, int index, int target, vector<int>& coins)
{
    if(target < 0)
    {
        return;
    }

    if(target == 0)
    {
        result.push_back(currSoln);
    }

    for(int i = index; i < coins.size(); ++i)
    {
        stringstream ss;
        ss << coins[i];
        string newCurrSoln = currSoln + ss.str() + " ";
        solve(result, newCurrSoln, i, target - coins[i], coins);
    }
}

但是，当我尝试使用DP来解决问题时，我陷入了困境。 我有两个主要障碍：

1. 我不知道应该使用什么数据结构来存储以前的答案
2. 我不知道我的自下而上的程序（使用循环代替递归）应该是什么样子。

欢迎任何帮助，一些代码将不胜感激！

感谢您的宝贵时间。

Answer 1

在 dp 解决方案中，您生成一组中间状态，以及有多少种方法可以到达这些状态。 那么你的答案就是最终处于成功状态的数字。

因此，对于找零计数，状态是您获得了特定的找零金额。 计数是做出改变的方式的数量。 成功的状态是您做出了正确数量的改变。

要从计算解决方案到枚举它们，您需要保留这些中间状态，并在每个状态中保留转换到该状态的所有状态的记录 - 以及有关如何转换的信息。 （在计算找零的情况下，如何添加就是您添加的硬币。）

现在有了这些信息，您可以从成功状态开始，递归地“向后”遍历 dp 数据结构，以实际找到解决方案而不是计数。 好消息是，您所有的递归工作都是高效的 - 您始终只查看成功的路径，因此不要在不起作用的事情上浪费时间。 但如果有十亿个解决方案，那么就没有什么捷径可以快速打印出十亿个解决方案。 如果你想聪明一点，你可以把它变成一个可用的枚举。 例如，您可以说“我知道有 4323431 个解，第 432134 个解是什么？” 并且很快就能找到解决方案。

Answer 2