给定一个货币数组arr，其中的值都是正数，再给定一个正数sum,每个值都认为是一张货币，即使是相同的货币也认为是不同的值，求返回sum的方法数

r囧r小猫 2022-10-12 15:56 74阅读 0赞

问题描述：给定一个货币数组arr，其中的值都是正数，再给定一个正数sum,每个值都认为是一张货币，即使是相同的货币也认为是不同的值，求返回sum的方法数。

例如：arr = \{1,2,2\},sum = 3;此处就有两种方法，返回2。

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

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

1.1、核心代码如下：

/**
     * @author wanghuainan
     * @date 2021/7/6 16:32
     */
    public class NanDaoCoinsWay {
        public static void main(String[] args) {
            int[] arr = {1,2,3};
            System.out.println(".......");
            int aim = 3;
            int ans1 = coinsWay(arr, aim);
          
            System.out.println("ans1:"+ans1);
           
        }
    
    
        private static int coinsWay(int[] arr, int aim) {
            if(arr == null || arr.length == 0){
                return 0;
            }
            return processWay(arr,0,aim);
        }
    
        /**
         * 从左往右的尝试
         * @param arr
         * @param index
         * @param rest
         * @return
         */
        private static int processWay(int[] arr, int index, int rest) {
            if(rest < 0){
                return 0;
            }
            if(index == arr.length){//钱遍历完了
                return rest == 0 ? 1 : 0;
            }else {
              //  return processWay(arr,index + 1,rest) + processWay(arr,index + 1,rest - arr[index]); 可读性差
                int i = 0;
                int j = 0;
                i = processWay(arr,index + 1,rest);//没要indx位置的钱
                j = processWay(arr,index + 1,rest - arr[index]);//要了indx位置的钱
                return i + j;
            }
        }
        
    }

2、动态规划：

2.1、二维数组图示分析：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpdW1laV8xMjM_size_16_color_FFFFFF_t_70][]

int\[\]\[\] dp = new int\[N + 1\]\[aim + 1\];?号位置dp\[0\]\[aim\]就是返回的结果；左下角dp\[N\]\[0\] = 1 是默认值；从第N行依次向上计算值。

2.2、核心代码如下：

/**
     * @author wanghuainan
     * @date 2021/7/6 16:32
     */
    public class NanDaoCoinsWay {
        public static void main(String[] args) {
            int[] arr = {1,2,3};
            System.out.println(".......");
            int aim = 3;
        
            int ans2 = coinDp(arr, aim);
          
            System.out.println("ans2:"+ans2);
        }
    
        /**
         * 动态规划
         * @param arr
         * @param aim 可变参数
         * @return
         */
        private static int coinDp(int[] arr, int aim) {
            if(aim == 0){
                return 1;
            }
            int N = arr.length;
            int[][] dp = new int[N + 1][aim + 1];
            /**
             * 第N行0位置的数是1，第N行剩余位置的数默认是0，下面循环赋值时是从N-1行开始依次往上赋值
             * 类似于这行代码
             * if (index == arr.length) {
             * 	   return rest == 0 ? 1 : 0;
             *  }
             */
            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] + (rest - arr[index] >= 0 ? dp[index + 1][rest - arr[index]] : 0);
                }
            }
            return dp[0][aim];//主函数返回0、aim位置的数值
        }
    
    }

3、两种方案的执行结果：

![20210706170441766.png][]

到此、我们分析完成了此道算法的解决思路，其实这是一个相对比较简单的问题，此道题可以有很多种变化，相应的有不同的解决思路，下篇我们会做一下分享，敬请期待！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpdW1laV8xMjM_size_16_color_FFFFFF_t_70]: /images/20221005/f4abff6fee5348e1930496887eee8ab7.png
[20210706170441766.png]: /images/20221005/991a02e4d1ad47b2bdcd9ba951fdddaf.png