擅长:python、mysql、java
<p>如果你熟悉图论的话,这里有一种思考硬币兑换问题的方法,这可能是有用的。</p>
<p>假设您有一个按以下方式定义的图:</p>
<ul>
<li>从0到您感兴趣的价值(如39美分或其他),每单位货币(如便士)有一个节点</li>
<li>任何两个节点之间都有一个弧,由允许使用的硬币的值隔开(例如,如果允许使用镍币,则一个介于34美分和29美分之间的节点)</li>
</ul>
<p>现在你可以把换硬币的问题看作是一个从你的兴趣值降到零的最短路径问题,因为硬币的数量将与你路径中的弧的数量完全相同。</p>
<p>该算法不使用图论术语,但它做的基本上是相同的事情:外循环覆盖所有“分”(或节点,在图论框架中)和内循环覆盖从当前弧到下一个弧的所有弧(coinValueList中的值)。总之,他们在寻找从零到你感兴趣的价值的最短路径。(价值降到零,零升到价值,都无关紧要。不过,传统上我们会向下搜索到零。)</p>
<p>当我意识到许多问题可以被转化为图问题时,我才真正开始理解动态编程。(不过,要小心——不是所有人都能。有些是超图,有些甚至可能不是超图。但这对我帮助很大。)</p>