后端开发刷题 | 兑换零钱（动态规划）

描述

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

如果无解，请返回-1.

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

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

示例1

输入：

[5,2,3],20

返回值：

4

示例2

输入：

[5,2,3],0

返回值：

0

示例3

输入：

[3,5],2

返回值：

-1

思路分析：

1. 初始化变量：
   • Max = aim + 1：定义了一个全局最大值，用于初始化dp数组。这个值被设置为aim + 1，是因为如果dp数组中的某个值保持为Max，则表示无法用给定的硬币组成该金额。
   • dp = new int[aim + 1]：定义了一个dp数组，其中dp[i]表示组成金额i所需的最少硬币数。数组大小为aim + 1，因为需要包括目标金额本身。
   • Arrays.fill(dp, Max)：将dp数组的所有元素初始化为Max，即无法组成该金额的状态。
   • dp[0] = 0：初始化dp数组的第一个元素为0，表示组成金额为0所需的最少硬币数为0。
2. 动态规划过程：
   • 外层循环遍历目标金额i（从1到aim），表示当前要尝试组成的金额。
   • 内层循环遍历硬币数组arr，检查每个硬币的面值。
   • 如果当前硬币的面值arr[j]小于等于当前要组成的金额i，则尝试使用这枚硬币。通过dp[i] = Math.min(dp[i], dp[i-arr[j]] + 1)更新dp[i]的值。这里dp[i-arr[j]] + 1表示使用了一枚面值为arr[j]的硬币后，还需要多少硬币来组成剩余的金额i-arr[j]，然后加1表示当前使用的这枚硬币。
3. 返回结果：
   • 最后，dp[aim]存储了组成目标金额aim所需的最少硬币数。但是，如果dp[aim]仍然是初始化的Max值，说明无法用给定的硬币组成目标金额，因此返回-1。否则，返回dp[aim]。

代码：

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) {
        //定义一个全局最大值
        int max=aim+1;
        int[] dp=new int[aim+1];
        Arrays.fill(dp,max);//初始化数组
        dp[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];
    }
}