兑换零钱(一)

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
        if(aim == 0){
            return 0;
        }
        // 思路：每一个dp[i]都代表该dp[i]能否被找零，arr数组里面的数，代表dp[数]一定是能被找零的，接下来往后推即可
        int dp[] = new int[aim+1];
        Arrays.fill(dp,1,dp.length,aim+1);
        for(int i=1; i<=aim; i++){
            for(int coin : arr){
                if(i-coin < 0 || dp[i-coin]>=aim) continue;
                dp[i] = Math.min(dp[i-coin]+1,dp[i]);
            }
        }
        return dp[aim] == aim +1  ? -1 : dp[aim];
    }
}

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        dp = [aim+1 for i in range(aim+1)]
        dp[0] = 0
        for i in range(1, aim+1):
            for j in arr:
                if i >= j:
                    dp[i] = min(dp[i], dp[i-j]+1)
        return dp[aim] if dp[aim] < aim+1 else -1

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
        if(arr == null || arr.length == 0)
            return -1;
        Arrays.sort(arr);
        int[] res = new int[aim + 1];
        res[0] = 0;
        for(int i = 1; i < aim + 1; ++ i){
            int min = Integer.MAX_VALUE;
            for(int j = 0; j < arr.length; ++ j){
                int n = i - arr[j];
                if(n < 0)
                    break;
                else{
                    if(res[n] == Integer.MAX_VALUE)
                        continue;
                    else
                        min = Math.min(min, res[n] + 1);
                }
            }
            res[i] = min;
        }
        return res[aim] == Integer.MAX_VALUE ? -1 : res[aim];
    }
}

    public int minMoney(int[] arr, int aim) {
        //dp[i] 换得金额i能用的最少硬币数
        int[] dp = new int[aim + 1];
        //后面要比较最小值 所以每个dp的初始值都是aim+1 ， 考虑硬币额度全为1用aim枚能换aim额度 aim+1必然是越界值了
        Arrays.fill(dp, aim + 1);
        dp[0] = 0; //因为要给dp[1-1]做铺垫 所以dp[0]必须是0
        for (int i = 1; i < aim + 1; i++) {
            for (int j = 0; j < arr.length; j++) {
                //别越界 && 至少能换出来才换 && 能换的话 看看我用这枚硬币好 还是不用好 
                // && 如果能用硬币你不用的话（或者压根换不出来） 那代价可是MAX值 逼着你尽可能换
                if (i - arr[j] >= 0) dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1);
            }
        }
        //要是流程走下来 dp值是非法值 说明换不出来
        return dp[aim]==aim+1?-1:dp[aim];
    }

    public int minMoney (int[] arr, int aim) {
        int[]dp=new int[aim+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;//凑够0元不需要硬币
        for(int i=1;i<=aim;i++){//动态规划，i表示要凑够的钱数，从最小值开始计算
            for(int coin:arr){//对于每种货币，首先判断能否使用，即coin<=i
                if(i-coin>=0&&dp[i-coin]!=Integer.MAX_VALUE)//此外，得保证i-coin是可以凑成的
                    dp[i]=Math.min(dp[i],dp[i-coin]+1);
            }
        }
        return dp[aim]==Integer.MAX_VALUE?-1:dp[aim];//最后如果不能被修改，说明不能凑成
    }

class Solution {
public:

	int minMoney(vector<int>& arr, int aim) {
		vector<int> dp(aim+1, 1e9);

		//拼出0元只需要0个硬币
		dp[0] = 0;

		//计算拼出1到aim最少需要多少张货币
		for (int i = 1; i <= aim; i++)
		{
			for (int j = 0; j < arr.size(); j++)
			{
				//从dp[0]开始，在之前的状态上叠加
				//计算dp[6],6-arr[0]=1，而dp[1]==1e9,跳过
				//6-arr[1]=4,而dp[4]==2(拼出4块钱最少需要两张2块)，=》dp[6]=dp[4]+1=3
				//6-arr[2]=3,而dp[3]==1(拼出3块钱最少需要一张3块)，=》dp[6]=min(3,dp[3]+1)=2
				if (i - arr[j] >= 0 && dp[i - arr[j]] != 1e9)
					dp[i] = min(dp[i], dp[i - arr[j]] + 1);
			}
		}
		if (dp[aim] == 1e9)
			return -1;
		return dp[aim];
	}
};

这个问题是一个典型的动态规划问题，也被称为“完全背包问题”。我们可以使用动态规划来求解组成给定钱数aim所需的最少货币数。

首先，我们定义一个数组dp，其中dp[i]表示组成钱数i所需的最少货币数。初始时，我们将dp数组的所有元素都设置为一个较大的数（比如aim + 1），表示初始状态下无法组成任何钱数。然后，我们将dp[0]设置为0，表示组成钱数0不需要任何货币。

接下来，我们遍历数组arr中的每个货币面值，对于每个面值，我们再次遍历dp数组，从该面值开始，更新每个钱数所需的最少货币数。具体的更新方式是：如果当前钱数i可以由之前的某个钱数j（j < i）加上当前面值得到，并且使用当前面值组成钱数i所需的货币数比之前的更少，那么我们就更新dp[i]。

最后，我们检查dp[aim]的值，如果它仍然是我们初始设置的那个较大的数，说明无法组成钱数aim，返回-1；否则，返回dp[aim]作为结果。

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        # write code here
        dp = [aim + 1] * (aim + 1)  
        dp[0] = 0  

        for coin in arr:  
            for i in range(coin, aim + 1):  
                dp[i] = min(dp[i], dp[i - coin] + 1)  

        return dp[aim] if dp[aim] != aim + 1 else -1

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        dp = [aim+1]*(aim+1)
        dp[0]=0
        for i in range(1,aim+1):
            for j in arr:
                if j>i:
                    continue
                dp[i] = min(dp[i],dp[i-j]+1)
        return dp[aim] if dp[aim]!=aim+1 else -1

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
        vector<int>V(aim+1,0);
        int i=0;
        for(i=1;i<=aim;i++)
        {
            for(int j=0;j<=arr.size();j++)
            {
                if(j==arr.size())
                {if(V[i]==0)
                    V[i]=-1;
                    break;}
                
                if(arr[j]>i)
                continue;
                else {
                    if(V[i]>(V[i-arr[j]]+1)||V[i]==0)
                    if(V[i-arr[j]]!=-1)
                    V[i]=V[i-arr[j]]+1;
                }
            }
        }
        return V[aim];
    }
};

public class Solution {
    public int minMoney (int[] arr, int aim) {
        // 凑成i块钱所需要的最少货币数
        int[] dp = new int[aim + 1];
        Arrays.fill(dp, aim + 1);
        // 凑成0元需要0个货币数
        dp[0] = 0;
        // 先遍历货币
        for (int c : arr) {
            // 后根据货币数值遍历目标金额
            for (int i = c; i <= aim; i++) {
                // 将当前货币加入
                // 不将当前货币加入
                // 取个最小值
                dp[i] = Math.min(dp[i - c] + 1, dp[i]);
            }
        }
        // 如果目标金额的所需最少货币数是aim+1，说明凑不成aim
        return dp[aim] == aim + 1 ? -1 : dp[aim];
    }
}

public class Solution {
    public int minMoney (int[] arr, int aim) {
        // 凑成i块钱所需要的最少货币数
        int[] dp = new int[aim + 1];
        Arrays.fill(dp, aim + 1);
        // 凑成0元需要0个货币数
        dp[0] = 0;
        // 先遍历目标金额
        for (int i = 1; i <= aim; i++) {
            // 遍历货币
            for (int c : arr) {
                // 如果目标金额比货币值还小，直接跳过
                if (i < c) {
                    continue;
                }
                // 将当前货币加入
                // 不将当前货币加入
                // 取个最小值
                dp[i] = Math.min(dp[i - c] + 1, dp[i]);
            }
        }
        // 如果目标金额的所需最少货币数是aim+1，说明凑不成aim
        return dp[aim] == aim + 1 ? -1 : dp[aim];
    }
}

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        # 定义a[i]为组成i的最少货币数
        # 状态转移矩阵a[i] = min(a[i-arr[0]], a[i-arr[n]]) + 1
        # 输出值a[aim]
        # 边界条件： a[i]全部初始化为0即可

        a = [0] * (aim + 1)
        for i in range(1, aim+1):
            min_num = 9999
            for coin in arr:
                if i >= coin:
                    min_num = min(min_num, a[i-coin] + 1)
            a[i] = min_num
        return a[aim] if a[aim] < 9999 else -1

class Solution {
public:
    /**
     * 最少货币数
     * @param arr int整型vector the array
     * @param aim int整型 the target
     * @return int整型
     */
    int minMoney(vector<int>& arr, int aim) {
        // 时间复杂度O(N*aim)，空间复杂度O(aim)
        vector<int> dp(aim + 1, aim + 1);
        dp[0] = 0;
        for (int i = 1; i <= aim; ++i) {
            for (int j = 0; j < arr.size(); ++j) {
                if (i >= arr[j]) dp[i] = min(dp[i], dp[i - arr[j]] + 1);
            }
        }
        return dp[aim] == aim + 1 ? -1 : dp[aim];
    }
};

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
        if(aim == 0) return 0;
        if(arr.empty()) return -1;
        vector<int> dp(aim+1,0x3f3f3f3f);//当钱数为i的时候使用最少钱数
        //对应为位置赋值
        for(auto i:arr){
            if(i<=aim) dp[i] = 1;
        }
        
        for(int i = 0;i<=aim;i++){
            for(auto j:arr){
                if(i-j>=0&&dp[i]>dp[i-j]+1){
                    dp[i] = dp[i-j]+1;
                }
            }
        }
        if(dp[aim]==0x3f3f3f3f) return -1;
        else return dp[aim];
    }
};

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
 
    def minMoney(self , arr: List[int], aim: int) -> int:
        # write code here
        if len(arr) == 0:

            return -1
        dp = [aim+1] * (aim+1)
        dp[0] =  0

        for i in range(len(arr)):
            for j in range(arr[i], aim+1):
                dp[j] = min(dp[j-arr[i]]+1, dp[j])
        if dp[aim] == aim+1:
            return -1
        return dp[aim]

import java.util.*;


public class Solution {
    public int minMoney (int[] arr, int aim) {
        int[] dp = new int[aim+1];  // dp数组记录每一个目标金额，对应的最小找零数
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= aim; i++) {
            for (int money : arr) {
                if (i >= money && dp[i-money] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i-money]+1, dp[i]);
                }
            }
        }

        return dp[aim] == Integer.MAX_VALUE ? -1 : dp[aim];
    }
}