题解 | #兑换零钱(一)#

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

        // 算法核心：动态规划（由于状态转移是基于for循环的，因此记忆化搜索不能够与动态规划相媲美了）

        // 先处理特殊值
        if (aim == 0) {
            return 0;
        }
        if (arr.length == 0) {
            return -1;
        }
        // dp[i][j] - 考虑第i个及以后的币种，目标是凑齐j，所需要的最少货币数
        // 先统一初始化成Integer.MAX_VALUE
        int[][] dp = new int[arr.length + 1][aim + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }

        // 初始化：对于[arr.length][0]   - 钱用完了，且刚好余额为0，不需要兑换了    -> 0
        //            [arr.length][>0]  - 钱用完了，但余额还有剩余，这种兑法是错的 -> Integer.MAX_VALUE表示错误
        //            [][0]             - 钱没用完，但是余额已经正好为0，兑换结束  -> 0
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 0;
        }
        // 状态转移方程：考虑当前币值用n(0 ~ j/arr[i])次 - dp[i][j] = Math.min(n + dp[i + 1][j - n*arr[i]])
        // i - 从下（大）往上（小）推
        // j - 从左（小）往右（大）推
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 1; j < dp[0].length; j++) {
                int n = j / arr[i];
                int min = Integer.MAX_VALUE;
                for (int k = 0; k <= n; k++) {
                    int cur = dp[i + 1][j - k * arr[i]];
                    if (cur != Integer.MAX_VALUE) {
                        cur += k;
                    }
                    if (cur < min) {
                        min = cur;
                    }
                }
                dp[i][j] = min;
            }
        }
        // int result =  process(arr, 0, aim);
        int result = dp[0][aim];
        if (result == Integer.MAX_VALUE) {
            return -1;
        } else {
            return result;
        }
    }


    // 如果对递归方程没思路，可将以下【递归回溯】改写成【动态规划】:
    //      1.递归出口 -> 初始化条件
    //      2.递归分支 -> 状态转移方程

    // public int process (int[] arr, int i, int j) {
    //     // 递归出口
    //     if (i == arr.length) {
    //         if (j == 0) {
    //             // 刚好到达j，算作是一个货币数目
    //             return 0;
    //         } else {
    //             // 无效情况
    //             return Integer.MAX_VALUE;
    //         }
    //     }
    //     if (j == 0) {
    //         return 0;
    //     }

    //     // 递归分支
    //     // 考虑当前币种用几张
    //     int min = Integer.MAX_VALUE;
    //     for (int m = 0; m <= j / arr[i]; m++) {
    //         // 本币值用m张
    //         // 后续情况
    //         int next = Math.min(Integer.MAX_VALUE, process(arr, i + 1, j - m * arr[i]));
    //         // 检验有效性，加上本货币使用个数
    //         int cur = Integer.MAX_VALUE;
    //         if (next != Integer.MAX_VALUE) {
    //             // 有效
    //             cur = next + m;
    //         }
    //         if (cur < min) {
    //             min = cur;
    //         }
    //     }

    //     return min;
    // }
}