给出面值数组arr，其中的值都是正数且无重复。每个值都认为是一种面值，并且张数是无限的，现给出正数aim，求返回组成aim的方法数。

矫情吗；* 2022-10-13 02:55 103阅读 0赞

问题描述：给出面值数组arr，其中的值都是正数且无重复。每个值都认为是一种面值，并且张数是无限的，现给出正数aim，求返回组成aim的方法数。

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

组成方法如下：1+1+1+1、1+1+2、2+2，一个三种方法，因此返回 3

解决方案：从暴力递归到动态规划的解决思想。

1、暴力递归的解决方法，核心代码如下：

/**
     * @author wanghuainan
     * @date 2021/7/8 11:12
     */
    public class NanDaoCoinsWayNoLimit {
    
        public static void main(String[] args) {
            int[] arr = {1,2,3};
            int aim = 3;
            int ans1 = coinsWayNoLimit(arr, aim);
        
            System.out.println("ans1:"+ ans1);
        }
     
    
        /**
         * 暴力递归方案
         * @param arr
         * @param aim
         * @return
         */
        private static int coinsWayNoLimit(int[] arr, int aim) {
            if(arr == null || arr.length == 0 || aim < 0){
                return 0;
            }
            return processNoLimit(arr,0 ,aim);
        }
    
        private static int processNoLimit(int[] arr, int index, int rest) {
            if(index == arr.length){//已经到了最后一位，没钱了
                return rest == 0 ? 1 : 0;
            }
            int ways = 0;
            for(int zhang = 0;zhang * arr[index] <= rest; zhang++){
                ways += processNoLimit(arr,index + 1,rest - (zhang * arr[index]));
            }
            return ways;
        }
    
    }

2、动态规划的思想

2.1、二维数组图示如下：

arr = \{1,2,3\};aim = 3;int N = arr.length;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_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/8 11:12
     */
    public class NanDaoCoinsWayNoLimit {
    
        public static void main(String[] args) {
            int[] arr = {1,2,3};
            int aim = 3;
            int ans2 = dpNoLimit1(arr, aim);
            System.out.println("ans2:"+ ans2);
        }
     
        /**
         * 动态规划方案
         * @param arr
         * @param aim
         * @return
         */
        private static int dpNoLimit1(int[] arr, int aim) {
            int N = arr.length;
            int[][] dp = new int[N + 1][aim + 1];
            dp[N][0] = 1;//和为0时，无论数组中有多少值，只有一种方法。
            for(int index = N -1; index >= 0; index--){//从N-1行往上加
                for(int rest = 0;rest <= aim; rest++){//从左到右计算
                    int ways = 0;
                    for(int zhang = 0;zhang * arr[index] <= rest;zhang++){
                        ways += dp[index + 1][rest - (zhang * arr[index])];
                    }
                    dp[index][rest] = ways;
                }
            }
            return dp[0][aim];
        }
    
    }

3、优化后的动态思想，核心代码如下：

/**
     * @author wanghuainan
     * @date 2021/7/8 11:12
     */
    public class NanDaoCoinsWayNoLimit {
    
        public static void main(String[] args) {
            int[] arr = {1,2,3};
            int aim = 3;
            int ans3 = dpNoLimit2(arr, aim);
            System.out.println("ans3:"+ ans3);
        }
    
        /**
         * 优化后的动态规划方案
         * @param arr
         * @param aim
         * @return
         */
        private static int dpNoLimit2(int[] arr, int aim) {
            if (arr == null || arr.length == 0 || aim < 0) {
                return 0;
            }
            int N = arr.length;
            int[][] dp = new int[N + 1][aim + 1];
            dp[N][0] = 1;//和为0时，无论数组中有多少值，只有一种方法。
            for(int index = N -1; index >= 0; index--){//从N-1行往上加
                for(int rest = 0;rest <= aim; rest++){//从左到右计算
                    dp[index][rest] = dp[index + 1][rest];
                    if(rest - arr[index] >= 0){
                        dp[index][rest] += dp[index][rest - arr[index]];
                    }
                }
            }
            return dp[0][aim];
        }
    
      
    }

到此，改算法的解决方案分享完毕，写一篇我们继续分析类似的一道算法，敬请期待！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221005/2d51bdae0e344bfa81a9a70d2be13a76.png