我有问题，了解动态规划解决各种问题，特别是硬币找零问题：

给定值N，如果我们想做出改变对于N美分，而我们每个S = {S1，S2，...，钐}价值的硬​​币，有多少种方法，我们才能作出改变的无限供给？硬币的顺序并不重要。

例如，对于N = 4，S = {1,2,3}，有四种解决办法：{1,1,1,1}，{1,1,2}，{2,2}， {1,3}。所以输出应该4.对于N = 10和S = {2,5，3，6}，有五种解决办法：{2,2,2,2,2}，{2,2,3,3}， {2,2,6}，{2,3,5}和{5,5}。因此，输出应为5。

有这样的问题，其中的溶液是硬币满足量的最小数目的另一种变化。

这些问题看起来很相似，但解决方案是很不同的

可能的方式做出改变号码：这样做的最优子是 DP（M，N）= DP（M-1，N）+ DP（M，N-SM）其中DP是解的个数为所有硬币到第m个硬币和量=正

最小硬币的金额：这种情况的最优子是 DP [I] =最小值{DP [I-D1]，DP [I-D2]，... DP [I-DN]} + 1 其中i是总量和D1 .. DN重present每个硬币面额。

为什么是它的第一个必需的2-D阵列和第二一维阵列？为什么是对的方式，使不更改数最优子 DP [I] = DP [I-D1] + DP [I-D2] + DP ... [I-DN] 其中DP [i]为可以由硬币获得我量的方式的数目。这听起来合乎逻辑的我，但它会产生不正确的答案。为什么是对于需要在这一问题，但并不需要在最小量的问题？所述硬币第二维

链接的问题：

http://comproguide.blogspot.com/2013/ 12 /最小硬币变化problem.html http://www.geeksforgeeks.org/dynamic-programming-set- 7-硬币变/

在此先感谢。每一个网站，我去只是解释了如何解决工作，而不是为什么其他的解决方案不起作用。

解决方案 让有关的路数，先说说 DP（M，N）= DP（M-1，N）+ DP（M，N-SM）。这确实是正确的，因为无论是你可以用第m个面额，也能避免它。现在你说我们为什么不把它写成 DP [I] = DP [I-D1] + DP [I-D2] + DP ... [I-DN] 。好，这将导致过度计数，让我们的例子，其中n = 4米= 2和S = {1,3}。现在，根据您的解决方案DP [4] = DP [1] + DP [3]。 （假设1是一个基例DP [1] = 1）。现在DP [3] = DP [2] + DP [0]。 （再次DP [0] = 1由基的情况）。再次应用相同DP [2] = DP [1] = 1。因此，在总，你得到的答案为3，当它应该是刚2（（1,3）和（1,1,1,1））。它是因为 第二个方法对待（1,3）和（3,1），为两个不同的solution.Your第二种方法可以应用到的情况下顺序的事项，这也是一个标准的问题。

现在你的第二个问题，你说教派的最小数量可以 发现由 DP [I] =最小值{DP [I-D1]，DP [I-D2]，... DP [I-DN]} + 1 。嗯，这是正确的，因为在寻找最低面值，命令或没有顺序并不重要。为什么这是线性/ 1-D DP，以及虽然DP数组是一维的每个状态取决于至多m个状态的第一个解决方案不同，其中数组是2-D但每个状态取决于最多2个状态。因此，在这两种情况下，运行时间，这是（国家数*状态每种状态取决于数）是相同的是 O（NM）。因此，两者都是正确的，只是你的第二个解决方案，可以节省内存。因此，无论你可以找到它通过一维数组方法或2-D使用复发 DP（N，M）= MIN（DP（M-1，N），1 + DP（M，N-SM））。 （只需使用分在第一次复发）

希望我清除了疑惑，难道后，如果仍然有任何不明白。

I am having issues with understanding dynamic programming solutions to various problems, specifically the coin change problem:

"Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5."

There is another variation of this problem where the solution is the minimum number of coins to satisfy the amount.

These problems appear very similar, but the solutions are very different.

Number of possible ways to make change: the optimal substructure for this is DP(m,n) = DP(m-1, n) + DP(m, n-Sm) where DP is the number of solutions for all coins up to the mth coin and amount=n.

Minimum amount of coins: the optimal substructure for this is DP[i] = Min{ DP[i-d1], DP[i-d2],...DP[i-dn] } + 1 where i is the total amount and d1..dn represent each coin denomination.

Why is it that the first one required a 2-D array and the second a 1-D array? Why is the optimal substructure for the number of ways to make change not "DP[i] = DP[i-d1]+DP[i-d2]+...DP[i-dn]" where DP[i] is the number of ways i amount can be obtained by the coins. It sounds logical to me, but it produces an incorrect answer. Why is that second dimension for the coins needed in this problem, but not needed in the minimum amount problem?

LINKS TO PROBLEMS:

http://comproguide.blogspot.com/2013/12/minimum-coin-change-problem.html http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

Thanks in advance. Every website I go to only explains how the solution works, not why other solutions do not work.

解决方案

Lets first talk about the number of ways, DP(m,n) = DP(m-1, n) + DP(m, n-Sm). This in indeed correct because either you can use the mth denomination or you can avoid it. Now you say why don't we write it as DP[i] = DP[i-d1]+DP[i-d2]+...DP[i-dn]. Well this will lead to over counting , lets take an example where n=4 m=2 and S={1,3}. Now according to your solution dp[4]=dp[1]+dp[3]. ( Assuming 1 to be a base case dp[1]=1 ) .Now dp[3]=dp[2]+dp[0]. ( Again dp[0]=1 by base case ). Again applying the same dp[2]=dp[1]=1. Thus in total you get answer as 3 when its supposed to be just 2 ( (1,3) and (1,1,1,1) ). Its so because your second method treats (1,3) and (3,1) as two different solution.Your second method can be applied to case where order matters, which is also a standard problem.

Now to your second question you say that minimum number of denominations can be found out by DP[i] = Min{ DP[i-d1], DP[i-d2],...DP[i-dn] } + 1. Well this is correct as in finding minimum denominations, order or no order does not matter. Why this is linear / 1-D DP , well although the DP array is 1-D each state depends on at most m states unlike your first solution where array is 2-D but each state depends on at most 2 states. So in both case run time which is ( number of states * number of states each state depends on ) is the same which is O(nm). So both are correct, just your second solution saves memory. So either you can find it by 1-D array method or by 2-D by using the recurrence dp(n,m)=min(dp(m-1,n),1+dp(m,n-Sm)). (Just use min in your first recurrence)

Hope I cleared the doubts , do post if still something is unclear.