首页 > 代码库 > 一道动态规划的题目
一道动态规划的题目
题目描述：
Create a class called Football. In football, scores are incremented by either
2, 3, or 7 points. Given a numerical input (integer between 1 and 75)
representing a final score, calculate the number of all possible combinations
of (2, 3, 7) which add up to that score. The output should be the number of
combinations found. Here are a couple of examples:
input | output | combinations
1 0
4 1 (2, 2)
9 3 (2, 7), (2, 2, 2, 3), (3, 3, 3)
11 3 (2, 2, 7), (2, 2, 2, 2, 3), (2, 3, 3, 3)
Here is the method signature (be sure your method is public:
int fetchCombinations(int input)
We will check to make sure the input to this problem is valid.
其实就是一个根据输入的一个数和一个数组，计算出有多少种不同的组合方式使得只使用数组里面的数（可以重复）相加结果等于输入的数。
假设输入的数为11，数组为[2,3,7]，那么输出3，表示有三种不同的组合方式，分别是(2, 2, 7), (2, 2, 2, 2, 3), (2, 3, 3, 3)
我的有两种方案：
1、第一种使用的是强暴的递归方式，假设输入的数为N，数组为[a,b,c,d]，那么调用递归函数的定义为recursion(int num, List<Integer> result);
初始化的时候传入的list为空的，当num等于0的时候将result加入到结果集里面；如果小于0则说明这个result不是一种组合，直接返回；否则复制一份当前的数组内容，然后依次得将数组元素k加入到新创建的数组中，递归的调用函数recursion(num-k, new_result);这样递归完成之后就能够得到所有的结果集合了。
2、使用和动态规划类似的方法：
因为要计算一个数N的所有可能的组合，那么就相当于先计算出N-a、N-b，N-c，N-d的组合，然后分别向这些组合中都加入a、b、c或者d，但是计算子集合的时候可能存在一定的重复，所以可以使用一个map将计算的结果保存起来，然后在计算之前首先查看这个map就可以了。这个map的key是一个整数，value是一个二维数组，每一项是一个结果的组合。
通过上面的方法可以得到由数组元素相加之和等于输入参数的所有集合，但是这些集合肯定存在着重复，例如11=2+2+2+2+3，11=3+2+2+2+2因为这里要计算组合的数目，这种重复需要去除，这时就需要一种方案去除所有重复的组合，在这里也就是判断两个数组是否包含相同的元素（即使它们的顺序不一样）。
这里我使用了两种方案：
0、最普通的方案是直接比较，首先对两个数组排序，然后依次比较，时间复杂度为O（lgn）
1.使用素数相乘的方法，因为任意多个素数的乘积结果不可能由其他任意多个素数相乘得到，利用这一点，我们可以给输入数组中的a,b,c,d分别赋予一个素数，这里从小到大依次是2,3,5,7，那么就需要计算两个数组中出现的a,b,c,d分别用这几个素数代替相乘，如果两个数组的计算结果相同，那么这两个数组肯定是相同的元素。但是这里存在移除的可能，我使用的是int保存乘积的结果，假设N等于100，a=2，此时a对应的素数是2，那么这个结果的乘积的结果就是2的50次方。显然已经溢出了，但是溢出不会影响正确性，只不过这里我们使用了2这个素数，如果碰巧连续出现多于31个2，那么肯定会溢出，溢出的结果是乘积等于0了，这就会出现错误了，所以我的解决方案是不使用2了，第一个素数使用3.当然也可以使用1，只不过在判断乘积是否相等之前需要先判断两个数组的元素个数是否相等。
2、使用计数的方法，两个数组元素相同，也就等同于两个数组中a,b,c,d的出现次数是相同的。那么我只需要保存这些出现的次数，这显然比较整个数组要高效的多，我还利用java的hashcode方法根据数组中每个元素出现的次数得到该对象的哈希值，然后再equals方法再逐个比较出现的次数。这样可以保证正确性。
测试结果：这里输入的参数是50-60（因为大于60之后递归方式将慢的不可接受），输入的数组是[2,3,7]
1、使用递归的方式+使用素数去重的方案：
value = http://www.mamicode.com/50, result = 37, cost = 14499 ms>
2、使用递归方式 + 计数去重的方案
value = http://www.mamicode.com/50, result = 37, cost = 14882 ms>
3、使用非递归方式 + 素数去重的方案
<div><div align="left" style="font-family: Tahoma; orphans: 2; widows: 2;font-size:14px;"><span style="font-family:Consolas;font-size:12px;"><span style="font-size: 10pt;"></span></span></div><div><div align="left" style="font-family: Tahoma; orphans: 2; widows: 2;font-size:14px;"><span style="font-family:Consolas;font-size:12px;"><span style="font-size: 10pt;">value = http://www.mamicode.com/150, result = 290, cost = 230 ms
value = 155, result = 308, cost = 121 ms
value = 160, result = 328, cost = 252 ms
value = 165, result = 348, cost = 75 ms
value = 170, result = 369, cost = 104 ms
value = 175, result = 390, cost = 161 ms
value = 180, result = 412, cost = 86 ms
value = 185, result = 434, cost = 108 ms
value = 190, result = 457, cost = 97 ms
value = 195, result = 481, cost = 132 ms
value = 200, result = 505, cost = 157 ms
4、使用非递归的方式 + 计数去重的方案
<div><div align="left" style="font-family: Tahoma; orphans: 2; widows: 2;font-size:14px;"><span style="font-family:Consolas;font-size:12px;"><span style="font-size: 10pt;"></span></span></div><div><div align="left" style="font-family: Tahoma; orphans: 2; widows: 2;font-size:14px;"><span style="font-family:Consolas;font-size:12px;"><span style="font-size: 10pt;">value = http://www.mamicode.com/150, result = 290, cost = 290 ms
value = 155, result = 308, cost = 101 ms
value = 160, result = 328, cost = 98 ms
value = 165, result = 348, cost = 86 ms
value = 170, result = 369, cost = 139 ms
value = 175, result = 390, cost = 449 ms
value = 180, result = 412, cost = 87 ms
value = 185, result = 434, cost = 185 ms
value = 190, result = 457, cost = 113 ms
value = 195, result = 481, cost = 167 ms
value = 200, result = 505, cost = 132 ms
从测试结果来看，使用非递归方式显然要比递归的方式性能高出几个数量级，递归存在了太多的重复计算了。而对于去重的方案，两种方案相差不大吧，使用计数方式更加可靠一些，这种方式不需要为正确性担忧。
该程序还有更加优化的地方：采用非递归的方案的时候，可以将每一个数的计算放到多线程中，只不过要共享全局的缓存，这样应该可以提高性能。
代码地址：https://github.com/terry-chelsea/Algorithm/tree/master/src/tc/football 欢迎指正~~ |
一道动态规划的题目
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。