题解 | #兑换零钱(一)#

题目主要信息：

给定数组arr，arr中所有的值都为正整数且不重复
arr中每个值代表一种面值的货币，每种面值的货币可以使用任意
组成aim的最少货币数
如果无解，请返回-1

举一反三：

本题属于背包问题的一种简化版本，学习完本题的思路帮助你解决相似的背包问题。

方法一：动态规划（推荐使用）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

思路：

这类涉及状态转移的题目，可以考虑动态规划。

具体做法：

step 1：可以用 $d p [i]$ 表示要凑出i元钱需要最小的货币数。
step 2：一开始都设置为最大值 $a i m + 1$ ，因此货币最小1元，即货币数不会超过 $a i m$ .
step 3：初始化 $d p [0] = 0$ 。
step 4：后续遍历1元到aim元，枚举每种面值的货币都可能组成的情况，取每次的最小值即可，转移方程为 $d p [i] = m i n (d p [i], d p [i - a r r [j]] + 1)$ .
step 5：最后比较 $d p [a i m]$ 的值是否超过aim，如果超过说明无解，否则返回即可。

Java实现代码：

import java.util.*;
public class Solution {
    public int minMoney (int[] arr, int aim) {
        //小于1的都返回0
        if(aim < 1) 
            return 0;
        int[] dp = new int[aim + 1];
        //dp[i]表示凑齐i元最少需要多少货币数
        Arrays.fill(dp, aim + 1); 
        dp[0] = 0; 
        //遍历1-aim元
        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); 
            }
        }
        //如果最终答案大于aim代表无解
        return dp[aim] > aim ? -1 : dp[aim]; 
    }
}

C++实现代码：

class Solution {
public:
    int minMoney(vector<int>& arr, int aim) {
        //小于1的都返回0
        if(aim < 1) 
            return 0;
        //dp[i]表示凑齐i元最少需要多少货币数
        vector<int> dp(aim + 1, aim + 1);  
        dp[0] = 0; 
        //遍历1-aim元
        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); 
            }
        }
        //如果最终答案大于aim代表无解
        return dp[aim] > aim ? -1 : dp[aim]; 
    }
};

Python代码实现：

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        #小于1的都返回0
        if aim < 1: 
            return 0
        #dp[i]表示凑齐i元最少需要多少货币数
        dp = [(aim + 1) for i in range(aim + 1)] 
        dp[0] = 0
        #遍历1-aim元
        for i in range(1, aim + 1): 
            #每种面值的货币都要枚举
            for j in range(len(arr)): 
                #如果面值不超过要凑的钱才能用
                if arr[j] <= i: 
                    #维护最小值
                    dp[i] = min(dp[i], dp[i - arr[j]] + 1) 
        #如果最终答案大于aim代表无解
        if dp[aim] > aim: 
            return -1
        else:
            return dp[aim]

复杂度分析：

时间复杂度： $O(n\cdot aim)$ ，第一层遍历枚举1元到aim元，第二层遍历枚举n种货币面值
空间复杂度： $O (a i m)$ ，辅助数组dp的大小

方法二：空间记忆递归（扩展思路）

知识点：递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。