题目

描述

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
如果无解，请返回-1.
【要求】
时间复杂度 $O(n \times aim)$ ，空间复杂度 $O(n)$ 。

方法一

思路

输入值为面值数组 arr 和找零数 aim，所以我们可以创建一个二维数组 dp[m][n]，纵轴 m 表示所有面值，横轴 n 表示使用面值 m 支付时剩余零钱数。
当使用一张面值为arr[i]的货币，那么使用的货币数 +1 且剩余需找零数要减去当前货币面值，若不使用当前面值的货币，那么货币数为使用上一种类的货币的数量且剩余找零数不需要减去。选出两种方法之中货币数最少的那一个就是最优解。

具体步骤

1.创建二维辅助数组；
2.初始化第一种面值货币，若能整除，则在数组中添入使用张数；
3.从第二种面值货币开始，进行遍历计算从1~aim金钱所需的最少货币数；
4.dp[arr.length-1][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) {
 // 二维数组 dp[m][n], m 表示货币种类, n表示剩余找零
   int[][] dp = new int[arr.length][aim + 1];
   // 初始化第一种面值，若能被剩余找零整除，就在数组中填该货币使用的张数。
   for (int i = 1; i < aim + 1; ++i) {
       if (i % arr[0] == 0) {
           dp[0][i] = i / arr[0];
       }
   }
   for (int m = 1; m < arr.length; ++m) {
       for (int n = 1; n < aim + 1; ++n) {
           // 若当前面值大于剩余找零，则只能不使用此种货币
           if (arr[m] > n) {
               dp[m][n] = dp[m - 1][n];
           } else if (arr[m] == n) {
               dp[m][n] = 1;
           } else if (dp[m][n - arr[m]] != 0 &&  dp[m - 1][n] != 0) {
               // 若使用一张当前货币和不使用当前货币都有值，取最小那个
               dp[m][n] =Math.min(dp[m][n - arr[m]] + 1, dp[m - 1][n]);
           } else {
               // 若其中一个为 0，取不为 0 的那一个
               dp[m][n] = dp[m][n - arr[m]] != 0 ? dp[m][n - arr[m]] + 1 : dp[m - 1][n];
           }

       }
   }
   return dp[arr.length-1][aim] == 0 ? -1 : dp[arr.length-1][aim];
}
}

时间复杂度： $O(n*aim)$ ，双重循环；
空间复杂度： $O(n*aim)$ ，二维数组，辅助空间。

方法二

思路

方法一同时考虑了货币以及目标金钱，将其子问题划分为更小的金额数以及更小的货币集，但实际上只需要考虑目标金钱数即可。题目要求找出达到aim的最少货币数，可以转换成其子问题找出换aim-arr[i]的最少货币数，即存在以下递推公式：
$图片说明$
若是无法兑换则f(aim) = -1。
故可以创建一维数组dp[aim+1],存储从金钱数0~aim的每种金钱数所需的最少货币数。

具体步骤

1.创建dp数组，存储从1~aim所有金钱所需的最少货币数；
2.依据递推公式计算1~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) {
   // write code here
   // 不同金钱所需要的货币数
   int[] dp = new int[aim+1];
   dp[0] = 0;
   int i = 1;
   while(i <= aim){
       dp[i] = Integer.MAX_VALUE;
       for (Integer money : arr){
           int diff = i - money;
           if (diff < 0 || dp[diff] < 0){
               continue;
           }
           // 都不小于0，取最小值
           dp[i] = Math.min(dp[i],dp[diff]);
       }
       ++dp[i];
       ++i;
   }
   return dp[aim] < 0 ? -1 : dp[aim];
}
}

时间复杂度： $O(n*aim)$ ，双重循环；
空间复杂度： $O(aim)$ ，dp数组辅助运算。

题解 | #换钱的最少货币数#

题目

描述

方法一

思路

具体步骤

方法二

思路

具体步骤