常用的递归解法
package test;
public class CoinToSum2 {
private static final int[] COINS = new int[] { 1, 2, 5, 10, 20, 50 };
private static final int SUM = 100;
private static int cnt = 0;
public static void main(String[] args) {
System.out.println(System.currentTimeMillis());
calc(0, 0, "");
System.out.println("total " + cnt + " solutions. ");
System.out.println(System.currentTimeMillis());// 110 ms
}
private static void calc(int sum, int coinIndex, String pre) {
if (SUM == sum) {
++cnt;
}
for (int i = coinIndex; i < COINS.length; i++) {
if (SUM - sum >= 0) {
calc(sum + COINS[i], i, pre + " " + COINS[i]);
}
}
}
}
这个消耗时间大概在110ms,比第1个逊色多了。。。而且代码晦涩难懂、不好理解
分享到:
相关推荐
NULL 博文链接:https://hxz-qlh.iteye.com/blog/1141325
NULL 博文链接:https://hxz-qlh.iteye.com/blog/1141327
1..n 1..5 1,2,3,4,5 StringM..StringN Car2..car14 Car2,Car3,Car4,…,Car14 DayM..DayN Mon..Fri Mon,Tue,Wed,Thu,Fri MonthM..MonthN Oct..Jan Oct,Nov,Dec,Jan MonthYearM..MonthYearN Oct2001..Jan2002 Oct2001...
不同为1"的原则得到0,0001的第3位为0,0010的第3位为0,则异或结果的第3位得到0,0001的第2位为0,0010的第2位为1,则异或结果的第2位得到1,0001的第1位为1,0010的第1位为0,则异或结果的第1位得到1,组合起来...
VLAN网络可以是有混合的网络类型设备组成,比如:10M以太网、100M以太网、令牌网、FDDI、CDDI等等,可以是工作站、服务器、集线器、网络上行主干等等。 VLAN除了能将网络划分为多个广播域,从而有效地控制广播...
(1)进程调度属于低级处理机管理,即确定系统中哪个进程将获得CPU;而作业调度属于高级处理机管理,即确定系统中哪些作业将获得CPU。 (2)进程是一个具有一定独立功能的程序关于某个数据集合的一次运行...
现在把一定数量的字符放到小括号里,比如: "a(bc)*": 匹配 a 后面跟0个或者一个"bc"; "a(bc){1,5}": 一个到5个 "bc." 还有一个字符 '│', 相当于OR 操作: "hi│hello": 匹配含有"hi" 或者 "hello" 的 ...
那么所有排列的数量就与你原始明文的长度密切相关,比如10位,所有可能就是P10的全排列。不同密码,可能加密出同样的结果。但是如果把一个字符按64位或256位处理,短短的10位字符,已经不再只有P10的全排列个结果。 ...
1 逻辑类问题(A类)-指设计、编码中出现的计算正确性和一致性、程序逻辑控制等方面出现的问题,在系统中起关键作用,将导致软件死机、功能正常实现等严重问题; 接口类问题(B类)-指设计、编码中出现的函数和...
(1) 分数的输入如果直接输入“1/5”,系统会将其变为“1月5日”,解决办法是:先输入“0”,然后输入空格,再输入分数“1/5”。(2) 序列“001”的输入如果直接输入“001”,系统会自动判断001为数据1,解决办法...
10. 某电影中,只有一个layer1,其上放置一个有两个元件(test1 和test2)组合成的组合体, 选择这个组合体执行打散Ctrl+B,然后右键单击执行Distribute to layers,那末: □ A. 这个电影中将增加两个新层:layer2 ...
10 2.判定理盖 ............................................................................................................................................ 10 3.条件覆盖 .................................
单片机及嵌入式系统课程设计 学 院 专业班级 学 号 姓 名 指导老师 2016年 6 月 20 日 1. 设计目的 1. 巩固和掌握对"单片机及嵌入式系统"课程内容的认识和理解,提高应用水平。 2. 掌握汇编语言程序的编制方法。 3. ...
认真听课、多思考问题、多动手操作、有问题一定要问、多参与讨论、多帮组同学 五、 体系结构 oracle的体系很庞大,要学习它,首先要了解oracle的框架。oracle的框架主要由物理结构、逻辑结构、内存分配、后台进程...
文件为doc版,可自行转成txt,在手机上看挺好的。 本资源来自网络,如有纰漏还请告知,如觉得还不错,请留言告知后来人,谢谢!!!!! 入门学习Linux常用必会60个命令实例详解 Linux必学的60个命令 Linux提供...
1、 FACTORY —追 MM 少不了请吃饭了, 麦当劳的鸡翅和肯德基的鸡翅都是 MM 爱吃的东西, 虽然口味有所不同, 但不管你带 MM 去麦当劳或肯德基, 只管向服务员说“来四个鸡翅”就行 了。麦当劳和肯德基就是生产鸡翅...
Linux的最早起源是在1991年10月5日由一位芬兰的大学生Linux Torvalds (Torvalds@kruuna.helsinki.fi)写了 Linux核心程序的 0.02 版开始的,但其后的发展却几乎都 是由互联网上的 Linux社团(Linux Community)互通...
API之网络函数1. API之网络函数 WNetAddConnection 创建同一个网络资源的永久性连接 WNetAddConnection2 创建同一个网络资源的连接 WNetAddConnection3 创建同一个网络资源的连接 WNetCancelConnection 结束一...
in_”是从Windows XP专业版中提取的,只要换成 Windows 2000专业版中的这两个文件即可。 步骤4 安装结束后,你可以打开“控制面板→性能和选项→管理工具”查看“Internet信息服务管理”。再打开IE,在地址栏中输入...