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、 设计思想：

详细操作流程看下图：

-4、视频讲解链接B站视频讲解

-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[aim];
    }
};

Java版本：

import java.util.*;


public class Solution {
    /**
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public int minMoney (int[] arr, int aim) {
        // write code here
        int Max = aim + 1;//定一个全局最大值
        int []dp = new int[aim + 1];//dp[i]的含义是目标值为i的时候最少钱币数是多少。
        Arrays.fill(dp,Max);//把dp数组全部定为最大值
        dp[0] = 0;//总金额为0的时候所需钱币数一定是0
        for(int i = 1;i <= aim;i ++){// 遍历目标值
            for(int j = 0;j < arr.length;j ++){// 遍历钱币
                if(arr[j] <= i){//如果当前的钱币比目标值小就可以兑换
                    dp[i] = Math.min(dp[i],dp[i-arr[j]] + 1);


                }
            }
        }
        return dp[aim] > aim ? -1 : dp[aim];

    }
}

Python版本:

#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
    def minMoney(self , arr , aim ):
        # write code here
        dp = [aim + 1] * (aim + 1)#把dp数组全部定为最大值
        dp[0] = 0#总金额为0的时候所需钱币数一定是0
        for i in range(1,aim + 1):#遍历目标值
            for j in arr: #遍历钱币
                if j <= i:#如果当前的钱币比目标值小就可以兑换
                    dp[i] = min(dp[i],dp[i-j] + 1)
        if dp[aim] > aim:
            return -1
        else:
            return dp[aim]