动态规划java

动态规划对于算法来说经常被用到，在递归中起到优化的作用。但是动态规划并不是具体的一种算法，而是一种编程原理。

在计算大数据斐波那契序列中，如果按照原始的思路使用递归，就会冗余，从而导致溢出或计算时间过长，这时就要应用到动态规划的思想来减少那些重复的计算

一，首先这是原始的递归fibonacci

public class text {
	public static void main(String[] args) {
		int a=fib();
		System.out.print(a);
		}
	public static int fib(int n) {
		if(n==1||n==2) {
			return 1;
		}
		return fib(n-1)+fib(n-2);
	}
}

 为了能减少重复的计算，需要一个数组来储存数据

public class text {
	public static void main(String[] args) {
		int a = Fib();//传入参数
		System.out.print(a);
	}

	public static int Fib(int n) {// 原来的基础上进行减少重复
		int[] arrys = new int[n + 1];// 用一个数组记录
		for (int i = 0; i < arrys.length; i++) 
                         // 初始化为0
			arrys[i] = 0;
		return fib2(arrys, n); // 记录数组的递归
	}

	public static int fib2(int[] arrys, int n) {
		if (n <= 1) {
			return 1;// 小于等于1的返回
		}
		if (arrys[n] != 0) {// 已经计算过的，结束递归
			return arrys[n];
		}
		arrys[n] = fib2(arrys, n - 1) + fib2(arrys, n - 2);// 进行递归
		return arrys[n];
	}

}

优化后的递归减少了不必要的计算减少了时间的使用

需要更大数据的可以将int类型转化为long！