dp第一行dp[0][0..aim]的值表示只使用一张arr[0]货币的情况下，找某个钱数的最小张数。比如arr[0]=2，那么能找开的钱数仅为2, 所以令dp[0][2]=1。因为只有一张钱，所以其他位置所代表的钱数一律找不开，一律设为INT_MAX。第一列dp[0…N-1]表示找的钱数为0时需要的最少张数，钱数为0时完全不需要任何货币，所以全设为0即可。
剩下的位置从左到右，从上到下计算，dp[i][j]可能的值来自于以下两种情况
1.dp[i][j]的值代表在可以任意使用arr[0..i-1]货币的情况下，组成j所需要的最小张数。可以任意使用arr[0..i]货币的情况当然包括不使用arr[i]的货币，而只使用任意arr[0..j-1]货币的情况，所以dp[i][j]的值可能为dp[i-1][j]。
2.因为arr[i]只有一张不能重复使用，所以我们考虑dp[i-1][j-arr[i]]的值，这个值代表在可以任意使用arr[0..i-1]货币的情况下，组成j-arr[i]所需的最小张数。从钱数为j-arr[i]到钱数j,只用在加上这张arr[i]即可。所以dp[i][j]的值可能等于do[i-1][j-arr[i]]+1。
3.如果dp[i-1][j-arr[i]]中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 ( arr[0] <= aim ){
dp[0][arr[0]] = 1;
}
for(int i=1; i<len; i++){
for(int j=1; j<=aim; j++){
int leftup = INT_MAX;
if( j>=arr[i] && dp[i][j-arr[i]] != INT_MAX ){
leftup=dp[i-1][j-arr[i]]+1;
}
dp[i][j] = min( dp[i-1][j], leftup );
}
}
return dp[len-1][aim]==INT_MAX ? -1 : dp[len-1][aim];
}
题目3：给定数组arr,arr中所有的值都为正数且重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim代表要找的钱数，求换钱有多少种方法。
题解： 类比题目1，每个面值的钱可以使用任意多次，我们可以构造一个dp数组，如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]，而其他面额的则无法找开，所以将arr[0][3,6,9]初始化为1 除此之外其他值初始化为0表示无法找开。对于第一列dp[0..n][0] 中的每一个元素dp[i][0]表示用arr[i]组成面额为0的钱的最少货币数，完全不需要任何货币，即一种方法，初始化为1。
对于剩下的任意dp[i][j]，我们依次从左到右，从上到下计算，dp[i][j]的值下面的方法数的和：
•完全不用arr[i]的货币，只使用arr[0..i-1]货币时，方法数为dp[i-1][j]
•用1张arr[i]货币，剩下的钱用arr[0..i-1]货币组成时，方法数为dp[i-1][j-arr[i]]
•用2张arr[i]货币，剩下的钱用arr[0..i-1]货币组成时，方法数为dp[i-1][j-2*arr[i]]
•…
•用k张arr[i]货币，剩下的钱用arr[0..i-1]货币组成时，方法数为dp[i-1][j-k*arr[i]]
其实从第二种情况到第k种情况方法的累加值其实就是dp[i][j-arr[i]]的值，所以dp[i][j] = dp[i-1][j] + dp[i][j-arr[i]] 。
int countWays(vector<int> arr, int n, int aim) {
vector<vector<int>> dp( n, vector<int>(aim+1,0) );
for(int j=0; arr[0]*j<=aim; j++){
dp[0][arr[0]*j] = 1;
}
for (int i = 1; i<n; i++){
dp[i][0] = 1;
for (int j = 1; j <= aim; j++){
if (j - arr[i] >= 0)
dp[i][j] = dp[i - 1][j] + dp[i][j - arr[i]];
else
dp[i][j] = dp[i - 1][j];
}
}
return dp[n - 1][aim];
}
题目4：给定数组arr，arr中所有的值都为正数且重复。每个值代表一张钱的面值再给定一个整数aim代表要找的钱数，求换钱有多少种方法。
题解：类比题目2，也是每个钱只能使用一次，此处不做解释
给出一道例题及答案：
例题：