c++ - 使用动态规划改变的所有解决方案

Question

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

给定具有不同值(value)的不同类型的硬币，找到所有硬币配置以不重复地加起来等于某个总和。

在类里面，我们解决了求和的所有可能方式的数量以及求和的最少硬币数的问题。但是，我们从未尝试真正找到解决方案。

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

我附带了递归版本(为简单起见，我只打印了解决方案):

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 个是什么？”很快就能找到解决方案。