今天我们看一下动态规划的硬币找零问题，主要通过一系列编程题分析动态规划的规律，只要掌握这一规律，许多动态规划的相关问题都可以类比得到。
题目1：给定数组arr，arr中所有的值都是正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim代表要找的钱数，求组成aim的最少货币数。
举例：
arr[5,2,3]，aim=20。 4张5元可以组成20元，其他的找钱方案都要使用更多张的货币，所以返回4。
题解：
一眼看去这道题好像可以用贪心算法可解，但是仔细分析发现有些值是不可以的，例如arr[1,3,4]，aim=6 ：用贪心算法算最少钱数为3 (4+1+1)，但是我们可以明显的发现用两张3元的就够了，所以用贪心算法不可解。
其实这是一道经典的动态规划方法，我们可以构造一个dp数组，如果arr的长度为N，则dp数组的行数为N，列数为aim+1，dp[i][j] 的含义是：在可以任意使用arr[0..i]货币的情况下，组成j所需要的最小张数。
明白以上定义后我们初始化第一行与第一列，第一行dp[0][0..aim]中每一个元素dp[0][j]表示用arr[0]货币找开面额 j所需要的最少货币数，此时我们只能选取arr[0]这一张货币，所以只有arr[0]的整数倍的面额钱才可以找开，例如当arr[0]=3，aim=10时，只能找开3,6,9的货币，而其他面额的则无法找开，所以将arr[0][3,6,9]初始化为1,2,3 除此之外其他值初始化为整形int的最大值INT_MAX表示无法找开。对于第一列dp[0..n][0] 中的每一个元素dp[i][0]表示用arr[i]组成面额为0的钱的最少货币数，完全不需要任何货币，直接初始化为0即可。
对于剩下的任意dp[i][j]，我们依次从左到右，从上到下计算，dp[i][j]的值可能来自下面：
完全不使用当前货币arr[i]的情况下的最少张数，即dp[i-1][j]的值
只使用1张当前货币arr[i]的情况下的最少张数，即dp[i-1][j-arr[i]]+1
只使用2张当前货币arr[i]的情况下的最少张数，即dp[i-1][j-2*arr[i]]+2
只使用3张当前货币arr[i]的情况下的最少张数，即dp[i-1][j-3*arr[i]]+3
…..
以上所有情况中，最终取张数最小的，即dp[i][j] = min( dp[i-1][j-k*arr[i]]+k )( k>=0 )
=>dp[i][j] = min{ dp[i-1][j], min{ dp[i-1][j-x*arr[i]]+x (1<=x) } } 令x = y+1
=>dp[i][j] = min{ dp[i-1][j], min{ dp[i-1][j-arr[i]-y*arr[i]+y+1 (0<=y) ] } }
又有 min{ dp[i-1][j-arr[i]-y*arr[i]+y (0<=y) ] } => dp[i][ j-arr[i] ] ,所以，最终有：dp[i][j] = min{ dp[i-1][j], dp[i][j-arr[i]]+1 }。如果j-arr[i] < 0，即发生了越界，说明arr[i]太大了，用一张都会超过钱数j，此时dp[i][j] = dp[i-1][j]。
int coinChange(vector<int>& arr, int aim) {
int len = arr.size();
vector<vector<int>> dp(len, vector<int>(aim+1,0));
for(int i=1; i<=aim; i++){
dp[0][i] = INT_MAX;
if( i>=arr[0] && dp[0][i-arr[0]] !=INT_MAX ){
dp[0][i] = dp[0][i-arr[0]]+1;
}
}
for(int i=1; i<len; i++){
for(int j=1; j<=aim; j++){
int left = INT_MAX;
if( j>=arr[i] && dp[i][j-arr[i]] != INT_MAX ){
left=dp[i][j-arr[i]]+1;
}
dp[i][j] = min( dp[i-1][j], left );
}
}
return dp[len-1][aim]==INT_MAX ? -1 : dp[len-1][aim];
}
参见leetcode :
上面的问题还可以进行空间压缩，此处不再赘述。
上面说贪心算法不可解其实面值在部分情况下可以用贪心算法解决，如果可换的硬币的单位是 c 的幂，也就是 c0，c1，... ，ck ,其中整数 c>1，k>=1，一定可以用贪心算法，或者某些情况比如，面值为1，5，10，20，50，100时，贪心找零也一定有最优解。参见《挑战程序设计竞赛》第二版2.2.1节。
题目2： 给定数组arr，arr中所有的值都为正数，每个值仅代表一张钱的面值，再给定一个整数aim代表要找的钱数，求组成aim的最小货币数。
题解: 相对于上一题，这道题的arr中的钱只有一张，而不是任意多张，构造dp数组的含义也同上，但是此时略有不同，