给出货币数组arr，均为正数，每个值都认为是一张货币，认为值相同的货币都相同，现给出一个正数aim，返回组成aim的方法数

た入场券 2022-10-13 02:56 101阅读 0赞

问题描述：给出货币数组arr，均为正数，每个值都认为是一张货币，认为值相同的货币没有任何不同，现给出一个正数aim，返回组成aim的方法数。

例如：arr = \{1,2,1,1,2,1,2\}，aim = 4

方法：1+1+1+1、1+1+2、2+2

一共三种方法，因此返回3。

解决方案：此处我们采用暴力递归和动态规划两种思路解决问题。

1、暴力递归：从左往右的尝试思想

1.1、核心代码如下：

import java.util.HashMap;
    import java.util.Map;
    
    public class NanDaoCoinsWaySame {
        public static void main(String[] args) {
    
            int[] arr = new int[]{1, 2, 2,2};
            int aim = 3;
            int ans1 = coinsWays(arr, aim);
          
            System.out.println("ans1:"+ans1);
     
        }
    
        public static class Info{
            int[] coins;
            int[] zhangs;
    
            public Info(int[] c,int[] z){
                coins = c;
                zhangs = z;
            }
        }
    
        /**
         * 取出数组里面的每个元素的个数并去重
         * @param arr
         * @return
         */
        public static Info getInfo(int[] arr){
            HashMap<Integer,Integer> counts = new HashMap<>();
            for(int value : arr){
                if(!counts.containsKey(value)){
                    counts.put(value,1);
                }else {
                    counts.put(value,counts.get(value) + 1);
                }
            }
            int N = counts.size();
            int[] coins = new int[N];
            int[] zhangs = new int[N];
            int index = 0;
            for(Map.Entry<Integer,Integer> entry : counts.entrySet()){
                coins[index] = entry.getKey();
                zhangs[index] = entry.getValue();
                index ++;
            }
            return new Info(coins,zhangs);
        }
    
       
        /**
         * 暴力递归思想
         * @param coins
         * @param zhangs
         * @param index
         * @param rest
         * @return
         */
        private static int processWays(int[] coins, int[] zhangs, int index, int rest) {
            if(index == coins.length){
                return rest == 0 ? 1 : 0;
            }
            int ways = 0;
            for(int zhang = 0;zhang * coins[index] < rest && zhang < zhangs[index];zhang++ ){
                ways += processWays(coins,zhangs,index + 1,rest - coins[index]);
            }
            return ways;
        }
    }

2、暴力递归：从左往右的尝试思想

2.1、核心代码如下：

import java.util.HashMap;
    import java.util.Map;
    
    public class NanDaoCoinsWaySame {
        public static void main(String[] args) {
    
            int[] arr = new int[]{1, 2, 2,2};
            int aim = 3;
          
            int ans2 = nanDaodp1(arr, aim);
       
            System.out.println("ans2:"+ans2);
    
    
        }
    
        public static class Info{
            int[] coins;
            int[] zhangs;
    
            public Info(int[] c,int[] z){
                coins = c;
                zhangs = z;
            }
        }
    
        /**
         * 取出数组里面的每个元素的个数并去重
         * @param arr
         * @return
         */
        public static Info getInfo(int[] arr){
            HashMap<Integer,Integer> counts = new HashMap<>();
            for(int value : arr){
                if(!counts.containsKey(value)){
                    counts.put(value,1);
                }else {
                    counts.put(value,counts.get(value) + 1);
                }
            }
            int N = counts.size();
            int[] coins = new int[N];
            int[] zhangs = new int[N];
            int index = 0;
            for(Map.Entry<Integer,Integer> entry : counts.entrySet()){
                coins[index] = entry.getKey();
                zhangs[index] = entry.getValue();
                index ++;
            }
            return new Info(coins,zhangs);
        }
    
        /**
         * 动态规划思想
         * @param arr
         * @param aim
         * @return
         */
        private static int nanDaodp1(int[] arr, int aim) {
            if(arr == null || arr.length== 0 || aim < 0){
                return 0;
            }
            Info info = getInfo(arr);
            int[] coins = info.coins;
            int[] zhangs = info.zhangs;
            int N = coins.length;
            int[][] dp = new int[N + 1][aim + 1];
            dp[N][0] = 1;
            for(int index = N - 1;index >= 0;index--){
                for(int rest = 0;rest <= aim;rest++){
                    int ways = 0;
                    for(int zhang = 0;zhang * coins[index] <= rest && zhang <= zhangs[index];zhang++){
                        ways += dp[index + 1][rest - (zhang * coins[index])];
                    }
                    dp[index][rest] = ways;
                }
            }
            return dp[0][aim];
        }
    
    }

3、暴力递归：从左往右的尝试思想

3.1、核心代码如下：

import java.util.HashMap;
    import java.util.Map;
    
    public class NanDaoCoinsWaySame {
        public static void main(String[] args) {
    
            int[] arr = new int[]{1, 2, 2,2};
            int aim = 3;
            int ans3 = nanDaodp2(arr, aim);
            System.out.println("ans3:"+ans3);
    
        }
    
        public static class Info{
            int[] coins;
            int[] zhangs;
    
            public Info(int[] c,int[] z){
                coins = c;
                zhangs = z;
            }
        }
    
        /**
         * 取出数组里面的每个元素的个数并去重
         * @param arr
         * @return
         */
        public static Info getInfo(int[] arr){
            HashMap<Integer,Integer> counts = new HashMap<>();
            for(int value : arr){
                if(!counts.containsKey(value)){
                    counts.put(value,1);
                }else {
                    counts.put(value,counts.get(value) + 1);
                }
            }
            int N = counts.size();
            int[] coins = new int[N];
            int[] zhangs = new int[N];
            int index = 0;
            for(Map.Entry<Integer,Integer> entry : counts.entrySet()){
                coins[index] = entry.getKey();
                zhangs[index] = entry.getValue();
                index ++;
            }
            return new Info(coins,zhangs);
        }
    
        /**
         * 动态规划思想优化
         * @param arr
         * @param aim
         * @return
         */
        private static int nanDaodp2(int[] arr, int aim) {
            if(arr == null || arr.length == 0 || aim < 0){
                return 0;
            }
            Info info = getInfo(arr);
            int[] coins = info.coins;
            int[] zhangs = info.zhangs;
            int N = coins.length;
            int[][] dp = new int[N + 1][aim + 1];
            dp[N][0] = 1;
            for(int index= N - 1;index >=0;index--){
                for(int rest = 0;rest <= aim;rest++){
                    dp[index][rest] = dp[index + 1][rest];//从下面往上面赋值
                    if(rest - coins[index] >= 0){
                        dp[index][rest] += dp[index][rest - coins[index]];//从左边赋值
                    }
                    if(rest - coins[index] * (zhangs[index] + 1) > 0){
                        dp[index][rest] -= dp[index][rest - coins[index] * (zhangs[index] + 1)];
                    }
                }
            }
            return dp[0][aim];
        }
    
    }

4、三种方案，执行结果如下  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

到处，此算法分享完毕，举一反三，万变不离其宗，勤于练习和思考，定会进步很快。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221005/4c337ad66eaa4d4c9928bd46288db0e4.png