题目描述

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

示例1

输入

[5,2,3],20

返回值

4

示例2

输入

[5,2,3],0

返回值

0

示例3

输入

[3,5],2

返回值

-1

解题思路

  1. 典型的动态规划问题，如果输入值为一个以上，可以考虑使用二维数组。输入值为面值数组 arr 和找零数 aim，所以我们可以创建一个二维数组 dp[m][n]，纵轴 m 表示所有面值，横轴 n 表示使用面值 m 支付时剩余零钱数。
  2. 动态规划的问题需在解题之前明确阶段、状态、边界。每个阶段的任务都会推进状态的更新，最后到达边界时解决问题。本题中每个阶段的任务是“若当前剩余需找零数为 m 时，考虑是否使用一张当前面值的钱”，状态记录每个阶段任务计算出的数据，即本题中的使用货币的最小张数。数组从左上角开始计算，到右下角结束，所以边界为遍历完数组。
  3. “若当前剩余需找零数为 m 时，考虑是否使用一张当前面值的钱”是指当使用一张当前面值的货币，那么使用的货币数 +1 且剩余需找零数要减去当前货币面值，若不考虑使用当前面值的货币，那么货币数为使用上一种类的货币的数量且剩余找零数不需要减去。选出两种方法之中货币数最少的那一个就是最优解。
  4. 初始化第一种面值的数量 dp[0][?] = 剩余找零 / 当前面值，如果有余数则设为 0。
  5. 在 (3) 中描述的两种方法，如果最少货币数为 0 则不取

Java代码实现

public class Solution {
    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] = 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];
    }

    private int min (int a, int b) {
        return a < b ? a : b;
    }

}