算法32：针对算法31货币问题进行扩展，并对从左往右模型进行总结

本算法是在算法31的基础之上进行推理总结的，因此，在看本章之前，必须先去了解算法31，否则会觉得莫名其妙。

算法31的推理过程：

如果 x = y1 + y2 + y3 + y4 + y5 + y6.? ?x1 = y2 + y3 + y4?+ y5 + y6

那么 x = y1 + x1.? ?

根据以上推导公式，可以对时间复杂度进行优化。

之前我们对从左往右模型进行过总结，即：

1.?针对固定集合，值不同，就是讨论要和不要的累加和。算法30有完整的例子

2.?针对非固定集合，面值固定，张数无限。口诀就是讨论要与不要，要的话逐步讨论要几张的累加和。算法31有完整的例子

今天，我们讨论最后一种情况，即：

3. 针对非固定集合，面值固定，张数随机。也就是说有可能只有0张，1张，2张，甚至也是无限的情况。口诀就是在口诀2的基础之上要去除多余项

题目：

arr是货币数组，其中的值都是正数。再给定一个正数aim。 ?每个值都认为是一张货币， ?认为值相同的货币没有任何不同， ?返回组成aim的方法数 。

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

方法：1+1+1+1、1+1+2、2+2 ?一共就3种方法，所以返回3。

也就是说，所有的1都是面值相同的，没有什么区别。

举个例子：给你6个1毛钱硬币，一个5毛钱硬币，要求你列举出能凑成1元钱的组合。答案肯定是1种呀，你不可能说每个1毛钱都是不一样，6个一毛轮流拿掉一个，剩余的和5毛钱组合，总共有5种组合方法吧。

下面说一下今天的推导公式。

假设某一行的value为3， 张数为2，aim还是15.??

那么基于算法31，我们可以对算法32进行假设：

是不是会有人问, 算法31不是会把y4，y5，y6等等情况都列举出来的吗，为什么本章算法就假设了value为3，张数只为2的情况呢。因为本算法每个面值的张数是不固定的，随机的。如果张数足够多，那逻辑就和算法31一样了。

思路：

1. 首先，我们需要对数组的每个面值以及对应的张数进行统计

2. 在讨论要不要，以及要几张的时候，需要在算法31的基础之上考虑实际可能存在的张数。

递归代码：

static class Info {
        int[] value;
        int[] zhangshu;

        Info (int[] k, int[] v) {
            value = k;
            zhangshu = v;
        }
    }

    public static Info getInfo (int[] arr) {
        Map map = new HashMap<Integer, Integer>();
        for (int i = 0; i < arr.length; i++) {
            int v = arr[i];
            if (map.get(v) != null) {
                map.put(v, (int) map.get(v) + 1);
            }
            else {
                map.put(v, 1);
            }
        }

        int[] k = new int[map.size()];
        int[] v = new int[map.size()];
        int index = 0;
        for (Iterator iterator = map.keySet().iterator(); iterator.hasNext();) {
            int key = (int) iterator.next();
            int value = (int) map.get(key);
            k[index] = key;
            v[index++] = value;
        }
        return new Info(k, v);
    }

    public static int ways(int[] arr, int aim)
    {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        Info info = getInfo(arr);
        return process(info.value, info.zhangshu, 0, aim);
    }

    public static int process (int[] value, int[] zhangshu, int index, int aim)
    {
        //面值数组结束了
        if (index == value.length) {
            return aim == 0 ? 1 : 0;
        }

        int ways = 0;
        for (int zhang = 0; zhang <= zhangshu[index] && zhang * value[index] <= aim; zhang++) {
            ways += process(value, zhangshu, index+1, aim- zhang * value[index]);
        }

        return ways;
    }

动态规划版本：

//动态规划
    public static int ways2(int[] arr, int aim)
    {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }

        Info info = getInfo(arr);
        //数组值
        int[] value = info.value;
        //每个值对应的张数
        int[] zhangshu = info.zhangshu;

        int[][] dp = new int[value.length + 1][aim + 1];
        //最后一行的初始值
        dp[value.length][0] = 1;

        //数组值为行
        for (int row =  value.length - 1; row >= 0; row--) {
            //aim为列
            for (int col = 0; col <= aim; col++) {

                int ways = 0;
                for (int zhang = 0; zhang * value[row] <= col && zhang <= zhangshu[row]; zhang++) {
                    ways += dp[row + 1][col - (zhang * value[row])];
                }
                dp[row][col] = ways;
            }
        }
        return dp[0][aim];
    }

对动态规划进行时间复杂度优化

//动态规划 + 时间复杂度
    public static int ways3(int[] arr, int aim)
    {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }

        Info info = getInfo(arr);
        //数组值
        int[] value = info.value;
        //每个值对应的张数
        int[] zhangshu = info.zhangshu;

        int[][] dp = new int[value.length + 1][aim + 1];
        //最后一行的初始值
        dp[value.length][0] = 1;

        //数组值为行
        for (int row =  value.length - 1; row >= 0; row--) {
            //aim为列
            for (int col = 0; col <= aim; col++) {

                /**
                 * 此处的代码，就是 x = x1 + y1.
                 * 即包含了多余的值了
                 */
                dp[row][col] = dp[row + 1][col];
                if (col - value[row] >= 0) {
                    dp[row][col] += dp[row][col - value[row]];
                }

                /**
                 * row代表推理的value， col代表列的下标，即代表aim的值
                 *
                 * 如果col就是我们想要的值，那么我们必须根据张数往前找。
                 * 如果value为3，张数为2，col为15，
                 * 那么我们就应该得到下一行的列下标为 15, 12, 9的值。而
                 * 多余的下标就是下一行列为6的值。
                 *
                 * value数组代表面值不同的数组: 此处的value[row] = 3.
                 * zhangshu数组代表当前面值为3的张数。此处zhangshu[row] = 2.
                 * 那么多余的位置不就是：
                 * 15 - 3 *（2+1） = 6 吗？
                 */
                if (col - value[row] * (zhangshu[row] + 1) >= 0) {
                    //既然是多余的，那当然要减去多余的推导了。
                    dp[row][col] -= dp[row + 1][col - value[row] * (zhangshu[row] + 1)];
                }
            }
        }
        return dp[0][aim];
    }

完整代码以及添加对数器进行测试

package code03.动态规划_07.lesson4;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * arr是货币数组，其中的值都是正数。再给定一个正数aim。
 * 每个值都认为是一张货币，
 * 认为值相同的货币没有任何不同，
 * 返回组成aim的方法数
 * 例如：arr = {1,2,1,1,2,1,2}，aim = 4
 * 方法：1+1+1+1、1+1+2、2+2
 * 一共就3种方法，所以返回3
 */
public class ContainWaysLimitCountPaper_06 {

        static class Info {
            int[] value;
            int[] zhangshu;

            Info (int[] k, int[] v) {
                value = k;
                zhangshu = v;
            }
        }

        public static Info getInfo (int[] arr) {
            Map map = new HashMap<Integer, Integer>();
            for (int i = 0; i < arr.length; i++) {
                int v = arr[i];
                if (map.get(v) != null) {
                    map.put(v, (int) map.get(v) + 1);
                }
                else {
                    map.put(v, 1);
                }
            }

            int[] k = new int[map.size()];
            int[] v = new int[map.size()];
            int index = 0;
            for (Iterator iterator = map.keySet().iterator(); iterator.hasNext();) {
                int key = (int) iterator.next();
                int value = (int) map.get(key);
                k[index] = key;
                v[index++] = value;
            }
            return new Info(k, v);
        }

        public static int ways(int[] arr, int aim)
        {
            if (arr == null || arr.length == 0 || aim < 0) {
                return 0;
            }
            Info info = getInfo(arr);
            return process(info.value, info.zhangshu, 0, aim);
        }

        public static int process (int[] value, int[] zhangshu, int index, int aim)
        {
            //面值数组结束了
            if (index == value.length) {
                return aim == 0 ? 1 : 0;
            }

            int ways = 0;
            for (int zhang = 0; zhang <= zhangshu[index] && zhang * value[index] <= aim; zhang++) {
                ways += process(value, zhangshu, index+1, aim- zhang * value[index]);
            }

            return ways;
        }

    //动态规划
    public static int ways2(int[] arr, int aim)
    {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }

        Info info = getInfo(arr);
        //数组值
        int[] value = info.value;
        //每个值对应的张数
        int[] zhangshu = info.zhangshu;

        int[][] dp = new int[value.length + 1][aim + 1];
        //最后一行的初始值
        dp[value.length][0] = 1;

        //数组值为行
        for (int row =  value.length - 1; row >= 0; row--) {
            //aim为列
            for (int col = 0; col <= aim; col++) {

                int ways = 0;
                for (int zhang = 0; zhang * value[row] <= col && zhang <= zhangshu[row]; zhang++) {
                    ways += dp[row + 1][col - (zhang * value[row])];
                }
                dp[row][col] = ways;
            }
        }
        return dp[0][aim];
    }

    //动态规划 + 时间复杂度
    public static int ways3(int[] arr, int aim)
    {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }

        Info info = getInfo(arr);
        //数组值
        int[] value = info.value;
        //每个值对应的张数
        int[] zhangshu = info.zhangshu;

        int[][] dp = new int[value.length + 1][aim + 1];
        //最后一行的初始值
        dp[value.length][0] = 1;

        //数组值为行
        for (int row =  value.length - 1; row >= 0; row--) {
            //aim为列
            for (int col = 0; col <= aim; col++) {

                /**
                 * 此处的代码，就是 x = x1 + y1.
                 * 即包含了多余的值了
                 */
                dp[row][col] = dp[row + 1][col];
                if (col - value[row] >= 0) {
                    dp[row][col] += dp[row][col - value[row]];
                }

                /**
                 * row代表推理的value， col代表列的下标，即代表aim的值
                 *
                 * 如果col就是我们想要的值，那么我们必须根据张数往前找。
                 * 如果value为3，张数为2，col为15，
                 * 那么我们就应该得到下一行的列下标为 15, 12, 9的值。而
                 * 多余的下标就是下一行列为6的值。
                 *
                 * value数组代表面值不同的数组: 此处的value[row] = 3.
                 * zhangshu数组代表当前面值为3的张数。此处zhangshu[row] = 2.
                 * 那么多余的位置不就是：
                 * 15 - 3 *（2+1） = 6 吗？
                 */
                if (col - value[row] * (zhangshu[row] + 1) >= 0) {
                    //既然是多余的，那当然要减去多余的推导了。
                    dp[row][col] -= dp[row + 1][col - value[row] * (zhangshu[row] + 1)];
                }
            }
        }
        return dp[0][aim];
    }


    // 为了测试
    public static int[] randomArray(int maxLen, int maxValue) {
        int N = (int) (Math.random() * maxLen);
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = (int) (Math.random() * maxValue) + 1;
        }
        return arr;
    }

    // 为了测试
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }


    public static void main(String[] args) {
      /*  int[] arr = {1,2,1,1,2,1,2};
        int aim = 4;

        System.out.println(ways(arr, aim));
        System.out.println(ways2(arr, aim));*/

        int maxLen = 10;
        int maxValue = 20;
        int testTime = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr = randomArray(maxLen, maxValue);
            int aim = (int) (Math.random() * maxValue);
            int ans1 = ways(arr, aim);
            int ans2 = ways2(arr, aim);

            if (ans1 != ans2) {
                System.out.println("Oops!");
                printArray(arr);
                System.out.println(aim);
                System.out.println(ans1);
                System.out.println(ans2);

                break;
            }
        }
        System.out.println("测试结束");
    }
}

至于空间复杂度优化，可以参考算法31进行研究，看看此题是否还可以对空间复杂度进行优化