题解 | 兑换零钱(一)

import java.util.*;


public class Solution {
    /**
     * 给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
     * 如果无解，请返回-1.
     * <p>
     * 很显然这是个完全背包问题：https://www.programmercarl.com/背包理论基础01背包-1.html#算法公开课
     * 可以使用动态规划求解
     * 定义 dp[i][j]，i: 代表可以使用的货币种类为 arr[0..i]，j: 代表需要兑换的面值数，其取值范围为[0..aim]，也就是说dp[i][j]表示：使用arr[0..i]，组成面值数为j的最少货币数。
     * 状态转移方程：
     * 如果不是用不是用第 i 张货币，那么 dp[i][j] = dp[i - 1][j]；
     * 如果使用第 i 张货币，则第 i 张货币的面值必须得小于 j
     * 那么 dp[i][j] = dp[i][j - arr[i]] + 1，表示使用 arr[0..i]组成面值数为 j-arr[i] 的最少货币数，再来一张 arr[i] 正好构成 j。
     * <p>
     * 初始化:
     * dp[0][j] = 0，表示仅使用 arr[0]对话换面值数为 j 的最少货币数，如果 j < arr[0]，则无法组成面值数为 j 的钱，使用一个较大值，表示无解;如果  j >= arr[0]，且 arr[0]可以被 j 整除，那么dp[0][j] = j/arr[0]。
     * dp[i][0]，表示使用 arr[0..i]组成面值数为 0 的最少货币数，显然为 0.
     * <p>
     * 优化：完全可以直接使用一个一维数组来存储状态转移方程，因为dp[i][j]只和dp[i-1][j]和dp[i][j-arr[i]]有关，所以只需要一个一维数组即可。
     * dp[j] = Math.min(dp[j], dp[j - arr[i]] + 1);
     * 初始化:dp[0]=0;其他为 aim+1
     */
    public int minMoney(int[] arr, int aim) {
        if (aim == 0) {
            return 0;
        }
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int[][] dp = new int[arr.length][aim + 1];
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < aim + 1; j++) {
                if (j == 0) {
                    dp[i][j] = 0;
                    continue;
                }
                if (i == 0 && j % arr[i] == 0) {
                    dp[i][j] = j / arr[i];
                } else {
                    dp[i][j] = aim + 1;
                }
            }
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j < aim + 1; j++) {
                if (j >= arr[i]) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - arr[i]] + 1);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[arr.length - 1][aim] > aim ? -1 : dp[arr.length - 1][aim];
    }
  
//  public int minMoney(int[] arr, int aim) {
//        if (aim == 0) {
//            return 0;
//        }
//        if (arr == null || arr.length == 0) {
//            return -1;
//        }
//        int[] dp = new int[aim + 1];
//        Arrays.fill(dp, aim + 1);
//        dp[0] = 0;
//
//        for (int i = 1; i < arr.length; i++) {
//            for (int j = 1; j < aim + 1; j++) {
//                if (j >= arr[i]) {
//                    dp[j] = Math.min(dp[j], dp[j - arr[i]] + 1);
//                }
//            }
//        }
//        return dp[aim] > aim ? -1 : dp[aim];
//    }
}