algorithm - 使用动态编程输出解决方案的好技术是什么？

Question

这个问题专门针对硬币找零问题。我知道找到用于找到任何数量的零钱的最佳硬币数量的算法，我也理解它，但我不明白的是，如果你愿意找到这种解决方案的路径，我怎么能“标记”。我曾尝试使用父指针，我确信这是这样做的方法，但我根本不知道我将如何实现它。这是一个例子。示例：给定硬币面额：1、10、25 找零：30 最佳解决方案需要：3 个硬币使用的硬币：10、10、10

我不太擅长解决动态规划问题。

Answer 1

你知道 T[30] = 3。你必须找到一个 T[30-c] = 2，尝试 {1,10,25} 中的所有 c。由于 T[30-10] = 2，您知道您将使用 10 美分硬币，现在必须解决 T[20] 的问题。

重复此操作直到 T[0] = 0。