题目描述
给你一类货币，货币的张数可以是任意的，然后给你一个aim 目标值，让你找出能兑换出 aim 钱数的最少货币的数量。
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
题目分析
我们先可以按照题目画出一个表，这个表纵轴代表 0 ~ N-1 每种相应的货币，横轴代表从0~aim的钱数。
现在如图，我们可以分析，dp[i][j]的结果是由从0 ~ i-1 种货币中，用了0张 arr[i]，用了一张 arr[i],用了俩张 arr[i] ,一直到用了k 张 arr[i] 的所有最小组成货币数中的最小值。这个k就是最多有k张 arr[i] 来构成 aim j的最小货币数。
即 dp(i,j) = min { dp[i-1][j]+0, dp[i-1][j-arr[i]]+1 , … , dp[i-1][j-arr[i]*k]+k} k>=0
现在化简这个公式：
??dp[i][j] = min { dp[i-1][j], min{dp[i-1][j-arr[i]]+…+dp[i-1][j-arr[i]*x]+x} x>=1 }
??dp[i][j] = min{ dp[i-1][j], min{dp[i-1][j-arr[i]-arr[i]*0] ,dp[i-1][j-arr[j-arr[i]-arr[i]*y]} y+1>=1}
??min{dp[i-1][j-arr[i]-arr[i]*0] ,dp[i-1][j-arr[i]-arr[i]*y]} y>=0} = dp[i][j-arr[i]]
综上
??dp[i][j] = min { dp[i-1][j] , dp[i][j-arr[i]]+1}
??最终这个公式的字面意思就是，dp[i][j]这个位置是由 0~i-1 个货币组成的最小货币数 和 0~i 种货币 组成 aim-arr[i] 货币的最小货币数 ， 这俩个中最小的一种。
初始条件
??初始条件第一列全初始化为0，因为构造0元的最小货币数都是0，第一行可以初始化，只能使用 arr[0] ,构成每一个aim,那么相应的dp值就是 j / arr[0]。
代码
int coinChange(vector<int>& v, int aim)
{vector<vector<int>> res(v.size());for (auto & i : res){i.resize(aim + 1);}int Rows = v.size();int Cols = res[0].size();for (int i = 0; i < Rows; ++i){res[i][0] = 0;}for (int j = 0; j < Cols; ++j){res[0][j] = (j%v[0] == 0) ? j / v[0] : 0x7ffffff;}for (int i = 1; i<Rows; ++i){for (int j = 1; j<Cols; ++j){if ((j - v[i]>=0) && ((res[i][j - v[i]] + 1)<res[i - 1][j])){res[i][j] = res[i][j - v[i]]+1;}else{res[i][j] = res[i - 1][j];}}}if (res[Rows - 1][Cols - 1] == 0x7ffffff)return -1;return res[Rows - 1][Cols - 1];
}
/*****************空间优化版********************/int coinChange(vector<int>& coins, int amount) {int Max = amount + 1;vector<int> dp(amount + 1, Max);dp[0] = 0;for (int i = 1; i <= amount; i++) {for (int j = 0; j < coins.size(); j++) {if (coins[j] <= i) {dp[i] = min(dp[i], dp[i - coins[j]] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];}
扩展
??不在给你货币的种类的数组，给你一个数组，里面每个下标的值仅能使用一次构成aim 的最小货币数。（有重复的货币）
分析
??实际上这个扩展使这个问题更加的简单化了，dp[i][j] = min { dp[i-1][j],dp[i-1][j-arr[i]]+1 } ，即要么没使用 ， 要么使用了1 张。
int coinChange2(vector<int>& v, int aim)
{vector<vector<int>> res(v.size());for (auto & i : res){i.resize(aim + 1);}int Rows = v.size();int Cols = res[0].size();for (int i = 0; i < Rows; ++i){res[i][0] = 0;}for (int j = 0; j < Cols; ++j){if (v[0] / j == 1)res[0][j] = 1;elseres[0][j] = 0x7ffffff;}for (int i = 1; i<Rows; ++i){for (int j = 1; j<Cols; ++j){if ((j - v[i] >= 0) && ((res[i-1][j - v[i]] + 1)<res[i - 1][j])){res[i][j] = res[i-1][j - v[i]] + 1;}else{res[i][j] = res[i - 1][j];}}}if (res[Rows - 1][Cols - 1] == 0x7ffffff)return -1;return res[Rows - 1][Cols - 1];
}