文档章节

递归与动态规划

memristor
 memristor
发布于 2014/04/17 15:19
字数 741
阅读 910
收藏 15

递归:将问题分解成子问题求解,从较小的问题逐渐逼近原始问题,很多时候只需要在f(n-1)中加入或移除某些东西或稍作修改就可以求得f(n)

动态规划与递归的区别:动态规划要将中间的结果缓存起来以备后续使用

1、斐波那契数列问题

public class fibonacci {

	private final static int max=1000;
	
	/**
	 * 递归方法,时间复杂度2^i
	 * @param i
	 * @return
	 */
	public static long recursion(int i) {
		if (i == 0)
			return 0;
		if (i == 1)
			return 1;
		return recursion(i - 1) + recursion(i - 2);
	}
	
	
	private static long[] temp=new long[max];
	/**
	 * 动态规划方法,将中间结果缓存起来,时间复杂度 i
	 * @param i
	 * @return
	 */
	public static long dynamic(int i){
		if (i == 0)
			return 0;
		if (i == 1)
			return 1;
		if(temp[i]!=0){
			return temp[i];
		}
		temp[i]=dynamic(i-1)+dynamic(i-2);
		return temp[i];
	}

	public static void main(String[]args) {
		long startTime = System.currentTimeMillis(); // 获取开始时间
		System.out.println(recursion(40));
		long endTime = System.currentTimeMillis(); // 获取结束时间
		System.out.println("程序运行时间: " + (endTime - startTime) + "ms");
		
		long startTime2 = System.currentTimeMillis(); // 获取开始时间
		System.out.println(dynamic(40));
		long endTime2 = System.currentTimeMillis(); // 获取结束时间
		System.out.println("程序运行时间: " + (endTime2 - startTime2) + "ms");
	}
}

运行结果

102334155

程序运行时间: 1145ms

102334155

程序运行时间: 0ms

递归算法的空间效率很低,每次递归调用都会在栈上增加一层

参考:http://zhedahht.blog.163.com/blog/static/25411174200722991933440/

扩展:

用8个1*2的小长条去覆盖一个2*8的棋盘,要求完全覆盖棋盘,小长条彼此不重叠。求总共有多少总覆盖方法。

其实就是fibonacci数列

分析见 http://blog.csdn.net/xianliti/article/details/5684315


2、楼梯问题

楼梯有n阶台阶,一次可以上1阶,2阶,或3阶,计算有多少种上楼梯的方式

小孩上完楼梯最后一步即抵达第n阶的那一步,可能走1阶或2阶或3阶,最后一步可能是第n-1阶向上走1,或n-2向上走2,或n-3向上走3,同样用递归问题可以解决

public class stair {
	
	public static int getMethods(int num) {
		if (num<0) {
			return 0;
		}
		if (num==0) {
			return 1;
		}
		return getMethods(num-1)+getMethods(num-2)+getMethods(num-3);
	}

	public static void main(String[] args) {
		System.out.println(getMethods(6));
	}

}

输出结果为:

24

扩展:

用1分、2分和5分的硬币凑成1元,共有多少种不同的凑法?(华为机试题)

参考:http://wenwen.sogou.com/z/q57580139.htm

这个不能用上述方法,因为走楼梯不同顺序是不同的走法,而硬币的凑法则与顺序无关,写程序可用穷举法

public class coin {
	
	public static int getKinds(){
		int num=0;
		for (int i = 0; i < 21; i++) {
			for (int j = 0; j <= 100-5*i; j++) {
				for (int k = 0; k <= 100-5*i-2*j; k++) {
					if(5*i+2*j+k==100){
						num++;
					}
				}
			}
		}
		return num;
	}

	public static void main(String[] args) {
		System.out.println(getKinds());
	}

}

输出:

541


3、编写一个方法返回集合的所有子集



4、编写一个方法确定字符串的所有排列组合



© 著作权归作者所有

上一篇: apache日志
下一篇: java简易聊天程序
memristor
粉丝 45
博文 203
码字总数 176319
作品 0
长沙
程序员
私信 提问
递归和动态规划

递归算法就是通过解决同一问题的一个或多个更小的实例来最终解决一个大问题的算法。为了在C语言中实现递归算法,常常使用递归函数,也就是说能调用自身的函数。递归程序的基本特征:它调用自...

LoSingSang
2018/03/12
45
0
递归 (二)

原谅我好几天没写专栏,我去写放了两个月的 NOIP 题了…… 尾递归、非尾递归 首先,来两个概念:尾递归和非尾递归。 顾名思义,如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称...

BillAlen
2016/10/31
0
0
动态规划法(一)从斐波那契数列谈起

动态规划法与分治方法   动态规划(Dynamic Programming)与分治方法相似,都是通过组合子问题的解来求解原问题。不同的是,分治方法通常将问题划分为互不相交的子问题,递归地求解子问题,...

jclian91
2018/05/28
0
0
Dynamic Programming(动态规划)

Introduction 作为科班出身的程序员,算法还是得懂一点点的。------佚名(我)。 动态规划是一个看起来很高大上的名字,让人一听就很想知道这到底是个啥,所以我常常需要跟身边好奇的朋友们解释...

Mark1996
2018/06/23
0
0
LeetCode: Distinct Subsequence

问题描述: Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a string is a new string which is formed from the original stri......

ljie-PI
2013/12/23
109
0

没有更多内容

加载失败,请刷新页面

加载更多

Executor线程池原理与源码解读

线程池为线程生命周期的开销和资源不足问题提供了解决方 案。通过对多个任务重用线程,线程创建的开销被分摊到了多个任务上。 线程实现方式 Thread、Runnable、Callable //实现Runnable接口的...

小强的进阶之路
16分钟前
3
0
maven 环境隔离

解决问题 即 在 resource 文件夹下面 ,新增对应的资源配置文件夹,对应 开发,测试,生产的不同的配置内容 <resources> <resource> <directory>src/main/resources.${deplo......

之渊
今天
8
0
详解箭头函数和普通函数的区别以及箭头函数的注意事项、不适用场景

箭头函数是ES6的API,相信很多人都知道,因为其语法上相对于普通函数更简洁,深受大家的喜爱。就是这种我们日常开发中一直在使用的API,大部分同学却对它的了解程度还是不够深... 普通函数和...

OBKoro1
今天
4
0
轻量级 HTTP(s) 代理 TinyProxy

CentOS 下安装 TinyProxy yum install -y tinyproxy 启动、停止、重启 # 启动service tinyproxy start# 停止service tinyproxy stop# 重启service tinyproxy restart 相关配置 默认...

Anoyi
今天
0
0
Linux创建yum仓库

第一步、搞定自己的光盘 #创建文件夹 mkdir -p /media/cdrom #挂载光盘 mount /dev/cdrom /media/cdrom #编辑配置文件使其永久生效 vim /etc/fstab 第二步,编辑yun源 vim /ect yum.repos.d...

究极小怪兽zzz
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部