NC126换钱的最少货币数

NC126换钱的最少货币数

- 1、题目描述：

- 2、题目链接：

https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45?tpId=196&&tqId=37128&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
-3、 设计思想：

详细操作流程看下图：

-5、代码：
c++版本:

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 Max = aim + 1;//定一个全局最大值
        vector<int> dp(aim + 1, Max);//把dp数组全部定为最大值
        dp[0] = 0;//总金额为0的时候所需钱币数一定是0
        for (int i = 1; i <= aim; i ++) {// 遍历目标值
            for (int j = 0; j < arr.size();j ++) {// 遍历钱币
                if (arr[j] <= i) {//如果当前的钱币比目标值小就可以兑换
                    dp[i] = min(dp[i], dp[i - arr[j]] + 1);
                }
            }
        }
        return dp[aim] > aim ? -1 : dp