初学动态规划

class Solution {
public:
/**
* 最少货币数
* @param arr int整型vector the array
* @param aim int整型 the target
* @return int整型
*/
int minMoney(vector<int>& arr, int aim) {
// write code here
int n = arr.size();
int dp[n][aim+1];//定义数组元素的含义,当要找的钱数为j时，最少钱币数为dp[j]
for(int i = 0; i < n; i++){
dp[i][0] = 0;
}//定义初始值
for(int j = 1; j <= aim; j++){
dp[0][j] = 1e6;// 无法凑出数值为j的钱
if(j-arr[0] >= 0 && dp[0][j-arr[0]] != 1e6){
dp[0][j] = dp[0][j-arr[0]] + 1;// 仅使用第一种类型的货币
}
}
for(int i = 1; i < n; i++){
for(int j = 1; j <= aim; j++){
if(j - arr[i] >= 0 && dp[i][j - arr[i]] != 1e6) {
// 判断不使用当前种类的货币和仅使用一张当前种类的货币这两种情况下，哪一种方案使用的货币少
dp[i][j] = min(dp[i - 1][j], dp[i][j - arr[i]] + 1);
}else{
// 不使用当前种类的货币
dp[i][j] = dp[i - 1][j];
}
}
}</int>

    return dp[n-1][aim] == 1e6 ? -1 : dp[n - 1][aim];
}

};