Julia likes to build a good fun memory about dynamic programming design, coding experience. Let this one - coin change build up good memory about Dynamic Programming.
322 Coin change
http://www.cnblogs.com/grandyang/p/5138186.html
这道题只让我们求出最小的那种，对于求极值问题，我们还是主要考虑动态规划Dynamic Programming来做，我们维护一个一维动态数组dp，其中dp[i]表示钱数为i时的最小硬币数的找零，递推式为：
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
其中coins[j]为第j个硬币，而i - coins[j]为钱数i减去其中一个硬币的值，剩余的钱数在dp数组中找到值，然后加1和当前dp数组中的值做比较，取较小的那个更新dp数组
To be continued.
No comments:
Post a Comment