首页 > 试题广场 >

兑换零钱(一)

[编程题]兑换零钱(一)

热度指数：88280 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。

如果无解，请返回-1.

数据范围：数组大小满足 $0 \le n \le 10000$ ，数组中每个数字都满足 $0 < val \le 10000$ ， $0 \le aim \le 5000$

要求：时间复杂度 $O(n \times aim)$ ，空间复杂度 $O(aim)$ 。

示例1

输入

[5,2,3],20

输出

示例2

输入

[5,2,3],0

输出

示例3

输入

[3,5],2

输出

-1

备注:

算法知识视频讲解

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

发表于 2022-08-22 15:30:28 回复(0)

Python 3

Vivimore

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

发表于 2022-05-22 14:34:12 回复(0)

QNBZ

class Solution {
public:
int minMoney(vector<int>& arr, int aim) {
vector<int>dp(aim+1,aim+1);dp[0]=0;
for(int i=0;i<arr.size();i++)
{
for(int j=arr[i];j<=aim;j++)
dp[j]=min(dp[j],dp[j-arr[i]]+1);
}
if(dp[aim]==aim+1)return -1;
return dp[aim];
}
};

发表于 2021-12-28 08:02:12 回复(0)

Python

nlp_mon

def minMoney(self , arr , aim ):
# write code here
if not aim:
return 0
level =seen= {0}
res = 0
while level:
if aim in level:
return res
level = {a+c for a in level for c in arr if a+c <= aim}-seen
seen |= level
res += 1

return -1

发表于 2021-06-26 16:55:30 回复(0)

C/C++

HELLOWORLDTC

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

发表于 2021-06-05 21:21:12 回复(0)

柠檬都被我吃了

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

发表于 2020-10-04 11:46:26 回复(0)

Java

-SoFar°

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

发表于 2021-03-22 18:43:09 回复(3)

Java

callmejacky

占个楼

import java.util.*;


public class Solution {
    /**
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public static int minMoney (int[] arr, int aim) {
        int len = arr.length;
        //dp[i][j]的含义为:在可以任意使用arr[0...i]货币的情况下，组成j所需的最小张数。
        int dp[][] = new int[len][aim + 1];

        // 初始化
        for(int i = 0; i < len; i++){
            dp[i][0] = 0;
        }
        for(int j = 1; j <= aim; j++){
            dp[0][j] = Integer.MAX_VALUE;// 无法凑出数值为j的钱
            if(j-arr[0] >= 0 && dp[0][j-arr[0]] != Integer.MAX_VALUE){
                dp[0][j] = dp[0][j-arr[0]] + 1;// 仅使用第一种类型的货币
            }
        }

        // 更新
        for(int i = 1; i < len; i++){
            for(int j = 1; j <= aim; j++){
                if(j - arr[i] >= 0 && dp[i][j - arr[i]] != Integer.MAX_VALUE) {
                    // 判断不使用当前种类的货币和仅使用一张当前种类的货币这两种情况下，哪一种方案使用的货币少
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - arr[i]] + 1);
                }else{
                    // 不使用当前种类的货币
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

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

编辑于 2020-09-29 10:01:29 回复(2)

Java

花落梦里

    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];//最后如果不能被修改，说明不能凑成
    }

发表于 2021-03-25 18:49:52 回复(0)

YueqiLee

int minMoney(int* arr, int arrLen, int aim ) {
// write code here
int dp[aim+1];//初始化数组dp，长度aim+1，除了dp[0]=0其他都为-1
for(int i=1;i<aim+1;i++){
dp[i]=-1;
}
dp[0]=0;

for(int i=1;i<=aim;i++){//从1开始遍历到aim，依次算1到aim的最优解
for(int j=0;j<arrLen;j++){//设置变量j，遍历其中面值数组
//如果i的值大于面值并且dp[i-arr[j]]有最优解
if(arr[j]<=i&&dp[i-arr[j]]!=-1){
//如果金额i还没有计算或者dp[i]比正在计算的dp[i-arr[j]]+1大
if(dp[i]==-1||dp[i]>dp[i-arr[j]]+1)
//更新dp[i]
dp[i]=dp[i-arr[j]]+1;
}
}
}
return dp[aim];

}

发表于 2022-05-24 11:02:47 回复(1)

Python3

6神君

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

发表于 2023-09-26 18:39:55 回复(0)

抢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
        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];
    }
};

发表于 2023-07-02 11:14:36 回复(0)

Java

Zhima1234

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

发表于 2023-06-04 16:38:35 回复(0)

Python3

Namely

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

发表于 2023-03-03 10:20:19 回复(0)

C++

Spectre_

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

发表于 2022-11-08 11:28:06 回复(0)

OttO轮椅专卖

可以大于不一定要等于是吧......

发表于 2024-10-29 10:50:18 回复(0)

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

        // 算法核心：动态规划（由于状态转移是基于for循环的，因此记忆化搜索不能够与动态规划相媲美了）

        // 先处理特殊值
        if (aim == 0) {
            return 0;
        }
        if (arr.length == 0) {
            return -1;
        }
        // dp[i][j] - 考虑第i个及以后的币种，目标是凑齐j，所需要的最少货币数
        // 先统一初始化成Integer.MAX_VALUE
        int[][] dp = new int[arr.length + 1][aim + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }

        // 初始化：对于[arr.length][0]   - 钱用完了，且刚好余额为0，不需要兑换了    -> 0
        //            [arr.length][>0]  - 钱用完了，但余额还有剩余，这种兑法是错的 -> Integer.MAX_VALUE表示错误
        //            [][0]             - 钱没用完，但是余额已经正好为0，兑换结束  -> 0
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 0;
        }
        // 状态转移方程：考虑当前币值用n(0 ~ j/arr[i])次 - dp[i][j] = Math.min(n + dp[i + 1][j - n*arr[i]])
        // i - 从下（大）往上（小）推
        // j - 从左（小）往右（大）推
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 1; j < dp[0].length; j++) {
                int n = j / arr[i];
                int min = Integer.MAX_VALUE;
                for (int k = 0; k <= n; k++) {
                    int cur = dp[i + 1][j - k * arr[i]];
                    if (cur != Integer.MAX_VALUE) {
                        cur += k;
                    }
                    if (cur < min) {
                        min = cur;
                    }
                }
                dp[i][j] = min;
            }
        }
        // int result =  process(arr, 0, aim);
        int result = dp[0][aim];
        if (result == Integer.MAX_VALUE) {
            return -1;
        } else {
            return result;
        }
    }


    // 如果对递归方程没思路，可将以下【递归回溯】改写成【动态规划】:
    //      1.递归出口 -> 初始化条件
    //      2.递归分支 -> 状态转移方程

    // public int process (int[] arr, int i, int j) {
    //     // 递归出口
    //     if (i == arr.length) {
    //         if (j == 0) {
    //             // 刚好到达j，算作是一个货币数目
    //             return 0;
    //         } else {
    //             // 无效情况
    //             return Integer.MAX_VALUE;
    //         }
    //     }
    //     if (j == 0) {
    //         return 0;
    //     }

    //     // 递归分支
    //     // 考虑当前币种用几张
    //     int min = Integer.MAX_VALUE;
    //     for (int m = 0; m <= j / arr[i]; m++) {
    //         // 本币值用m张
    //         // 后续情况
    //         int next = Math.min(Integer.MAX_VALUE, process(arr, i + 1, j - m * arr[i]));
    //         // 检验有效性，加上本货币使用个数
    //         int cur = Integer.MAX_VALUE;
    //         if (next != Integer.MAX_VALUE) {
    //             // 有效
    //             cur = next + m;
    //         }
    //         if (cur < min) {
    //             min = cur;
    //         }
    //     }

    //     return min;
    // }
}

发表于 2024-09-24 14:48:49 回复(0)

Python3

要冲外企的鲸鱼很想run

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

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

发表于 2024-08-22 20:44:14 回复(0)

TokaiTeio_

#include <vector>
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>dp(aim + 1,1e8);
        dp[0] = 0;
        for(int i = 1; i <= aim; i ++ )
            for(auto it : arr)
                if(it <= i) dp[i] = min(dp[i - it] + 1,dp[i]);
        if(dp[aim] == 1e8) return -1;
        return dp[aim];
    }
};

发表于 2024-08-15 20:52:46 回复(0)

唐氏综合征

脑溢血做法：递归+回溯

public int minMoney(int[] arr, int aim) {
        // write code here
        int len = arr.length;
        if (len == 0)
            return -1;
        if (aim == 0)
            return 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minMoneyRecursiveHelper(arr, aim, 0, minHeap, len - 1);

        return minHeap.size() == 0 ? -1 : minHeap.poll();

    }

    public void minMoneyRecursiveHelper(int[] arr, int aim, int minCnt, PriorityQueue<Integer> queue, int index) {
        if (aim == 0) {
            queue.offer(minCnt);
            return;
        }
        if (index < 0 || aim < 0 || (queue.size() > 0 && minCnt >= queue.peek())) {
            return;
        }
        // 先递归，到最深, 如 len -1 =5 时，从 index =1 ~ 5 依次计算
        minMoneyRecursiveHelper(arr, aim, minCnt, queue, index - 1);
        // 第一个递归弹栈时，index = 0,1,2...，类似于回溯
        minMoneyRecursiveHelper(arr, aim - arr[index], minCnt + 1, queue, index);
    }

动态规划数组解法：

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) {
        // 如果目标金额为0，则不需要任何货币
        if (aim == 0) return 0;
        // dp[i] 表示凑成金额 i 所需的最少货币数
        int[] dp = new int[aim + 1];
        // 初始化为一个大数，代表无法凑成的情况
        Arrays.fill(dp, aim + 1);
        dp[0] = 0; // 凑成金额0的货币数为0

        for (int i = 1; i <= aim; i++) {
            for (int coin : arr) {
                if (i >= coin) {
                    // 当前的次数 = 除去当前货币的次数  + 当前货币这次
                    // 内部循环，会尝试所有的可能情况，找到最小值
                    // 如果 dp[i - coin], dp[i] 未被更新，则会更新一个较大值
                    // 因此整个组合过程只要有一个凑不成，就会更新较大值，就代表无法组合
                    dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
                }
            }
        }

        // 如果dp[aim]为初始值，则表示无法凑成
        return dp[aim] > aim ? -1 : dp[aim];
    }
}

编辑于 2024-04-07 12:15:15 回复(0)

提交观点

问题信息

动态规划

难度：

115条回答 1097收藏 5997浏览

通过挑战的用户

查看代码

牛客89418...

2022-10-26 20:19:52
牛客74843...

2022-10-10 20:56:54
牛客80946...

2022-09-16 16:40:28
LeeZhiyu

2022-09-16 15:48:40
DragonN...

2022-09-16 15:01:37

兑换零钱(一)

输入

输出

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题