class Solution { public: /** * 最少货币数 * @param arr int整型vector the array * @param aim int整型 the target * @return int整型 */ //转移方程 //f[aim] = std::min(f[aim - arr[0]]+1,f[aim - arr[1]]+1, .....) int minMoney(vector<int>& arr, int aim) { // write code here if(arr.empty() || aim < 0) { return -1; } if (aim == 0) { return 0; } vector<int> dp(aim + 1, INT_MAX - 1); dp[0] = 0; for (int i = 1; i <= aim; i++) { for (int j = 0; j < arr.size(); j++) { if ((i - arr[j]) >= 0 && dp[i - arr[j]] != INT_MAX - 1) { // 边界处理 dp[i] = std::min(dp[i], dp[i - arr[j]] + 1); } } } return dp[aim] == INT_MAX - 1? -1 : dp[aim]; } };