本算法是在算法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进行研究，看看此题是否还可以对空间复杂度进行优化