题目

描述

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

方法一

思路

• 输入值为面值数组 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];
  }
  }

• 时间复杂度：，双重循环；

• 空间复杂度：，二维数组，辅助空间。

方法二

思路

• 方法一同时考虑了货币以及目标金钱，将其子问题划分为更小的金额数以及更小的货币集，但实际上只需要考虑目标金钱数即可。题目要求找出达到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];
  }
  }

• 时间复杂度：，双重循环；
• 空间复杂度：，dp数组辅助运算。