qui*_*ack 6 recursion dynamic-programming
我遇到了两个动态编程问题.其中一个问题是
考虑到我可以一次跳1步,2步或3步,爬楼梯的步数是多少.
用于解决该问题的动态编程方法如下.
If C(n) is number of ways of climbing the staircase, then
C(n) = C(n-1) + C(n-2) + C(n-3) .
This is because , if we reach n-1 stairs, we can hop to n by 1 step hop or
if we reach n-2 stairs, we can hop to n by 2 step hop or
if we reach n-3 stairs, we can hop to n by 3 step hop
正如我想要的那样,我理解了上述方法,我遇到了硬币变化问题
给出无限数量的25美分硬币,10美分硬币(硬币),5美分硬币(镍币)和1美分硬币,代表n美分的方式数量是多少
事实证明,这个问题的解决方案与上面的解决方案不同,并且有点复杂.即, C(n)= C(n-1)+ C(n-5)+ C(n-10)+ C(n-25)不成立.我仍然试图理解解决这个问题的方法.但我的问题是硬币变化问题与更简单的攀爬步骤问题有何不同？
在步骤问题中，顺序很重要：(1,2) 与 (2,1) 不同。对于硬币问题，只有使用的每种硬币的数量才重要。
Scott 的解决方案是绝对正确的，他提到了两个问题之间差异的症结所在。这里对这两个问题进行了更多的说明，以帮助直观地理解差异。
对于涉及递归的动态规划问题，诀窍是正确解决子问题。一旦子问题是正确的，就只是在此基础上进行构建。
楼梯问题处理序列，因此子问题更容易直观地看到。对于 Coin-change 问题，我们正在处理计数，因此子问题是关于是否使用特定面额的问题。我们使用面额计算解决方案的一部分，不使用面额计算另一部分。这是一个稍微难以理解的洞察力，但是一旦你看到它，你就可以递归计算其余的。
因此，这是考虑这两个问题的一种方法：
介绍一个新的步骤。已添加第 n 步。我们如何计算 S[N]？
S[N] = S[N-1] + S[N-2] + S[N-3]
介绍一种新的小硬币面额。假设新推出了一种面额为“m”的硬币。我们现在如何计算 C[n]，知道 C[N，除了 m] 之外的所有硬币？
没有硬币 m到达 N 的所有方法仍然成立。但是每个新的硬币面额“m”从根本上改变了获得 N 的方式。所以要计算 C[N using m] 我们必须递归计算 C[Nm，使用新硬币 m] 和 C[N-2m 使用 m ]...等等。
C[N, with m] = C[N, without m] + C[N-m, with m]
希望有帮助。