java 动态规划（找零钱）

电玩女神 2022-11-21 09:58 185阅读 0赞

--------------------

### java 动态规划（找零钱） ###

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* ###

**动态规划**

**算法描述：原问题可拆分为多个阶段进行，每个阶段都做出全局最优选择，并且当前阶段的选择与后续阶段选择无关（无后效性），以此得出原问题的全局最优解**

**应用举例：斐波那契数列**

f(0)=0,
    f(1)=1,
    f(n)=f(n-1)+f(n-2), n>=2、n为自然数

**可用解法：递归、递归+缓存（缓存重复计算的结果）、动态规划**

**动态规划求解：自底向上，依次计算f(2)、f(3) ... f(n)**

**全局最优：**f(n)计算的值唯一，是全局最优解

**无后效性：**f(n)的值只与f(n-1)、f(n-2)有关，与f(n+1)、f(n+2)无关

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* ###

**示例：找零钱**

**问题描述**

给定不同面额的硬币 coins 和一个总金额 amount,
    计算可以凑成总金额所需的最少的硬币个数(每种硬币的数量可认为是无限的),
    如果没有任何一种硬币组合能组成总金额，返回 -1。
    
    
    示例 1：coins = [1, 2, 5], amount = 11
    最少硬币个数：3, 11=5+5+1
    
    示例 2：coins = [2], amount = 3
    最少硬币个数：-1, 无解
    
    示例 3：coins = [1], amount = 0
    最少硬币个数：0, 不需要找零

public class MyTest2 {
    
        private static final Map<Integer,Integer> map=new HashMap<>();
    
        public static int fun(int[] coins,int amount){
            if (amount<0){
                return -1;
            }
    
            if (amount==0){
                return 0;
            }
    
            if (coins.length==0){
                return -1;
            }
    
            int min=Integer.MAX_VALUE;
            for (int coin : coins) {
                int result = fun(coins, amount-coin);
                if (result != -1 && min > result) {
                    min = result;
                }
            }
    
            if (min==Integer.MAX_VALUE){
                return -1;
            }else {
                return min+1;
            }
        }
    
        public static int fun2(int[] coins,int amount){
            if (map.get(amount)!=null){
                return map.get(amount);
            }
    
            if (amount<0){
                return -1;
            }
    
            if (amount==0){
                return 0;
            }
    
            if (coins.length==0){
                return -1;
            }
    
            int min=Integer.MAX_VALUE;
            for (int coin : coins) {
                int result = fun(coins, amount-coin);
                if (result != -1 && min > result) {
                    min = result;
                }
            }
    
            int result=-1;
            if (min!=Integer.MAX_VALUE){
                result=min+1;
            }
    
            map.put(amount,result);
            return result;
        }
    
        public static int fun3(int[] coins, int amount){
            if (amount==0){
                return 0;
            }
    
            if (coins.length==0){
                return -1;
            }
    
            int[] a=new int[amount+1];
            for (int i=1;i<=amount;i++){
                a[i]=-1;
            }
    
            int min=coins[0];
            for (int value : coins){
                if (min>value){
                    min=value;
                }
            }
    
            for (int i=0;i<=amount;i++){
                if ((i+min)>amount){
                    break;
                }
    
                if (a[i]==-1){
                    continue;
                }
    
                for (int value : coins){
                    if ((i+value)<=amount&&(i+value)>0){
                        if (a[i+value]==-1||a[i+value]>a[i]+1){
                            a[i+value]=a[i]+1;
                        }
                    }
                }
            }
    
            return a[amount];
        }
    
        public static void main(String[] args){
            int[] coins={1,2,5};
            int amount=21;
    
            System.out.println("递归求解："+fun(coins,amount));
            System.out.println("递归缓存求解："+fun2(coins,amount));
            System.out.println("动态规划求解："+fun3(coins,amount));
        }
    }

**控制台输出**

递归求解：5
    递归缓存求解：5
    动态规划求解：5

**说明：动态规划的时间复杂度为o(n)，计算使用的时间最短**