动态规划

在Fibonacci函数里面，最常规最简单的做法是用递归的方式。
F(n)=F(n-1)+F(n-2)就是费波那契数列的定义。
例如：
1 1 2 3 5 8 13，就是一个费波那契数列

public   static int Fibonacci(int n){
	if(n<=0){
		return 0;
	}
	if(n==1||n==2){
		return 1;
	}
	else{
		return Fibonacci2(n-1)+Fibonacci2(n-2);
	}
}

它的代码如上。
用递归很容易实现，但是也会出现一个问题，若n变的越来越大，效率会成指数增长，时间复杂度为O（2ⁿ）。
如果n过大，甚至可能会溢出内存（反正我n太大eclipse就没反应了）。

这是为什么呢？

这是f(n)，n从1到8所调用的函数

不难看出，如果要计算F（8），前面会计算很多次重复的数据。
如果我们先从F（1）开始算起，把计算的结果存储起来是否可以避免重复计算呢？
F(1)=1
F(2)=1
F(3)=F(1)+F(2)=2
F(4)=F(3)+F(2)=3
.
.
.
F(n)=F(n-1)+F(n-2)
创建一个数组，把前面的结果先存储起来，等后面的数据需要时直接调用，成为一个有效的解决办法。

工作效益问题

题：当前有N个工作，，每个工作有相应的收益，但是每个工作的时间不同，且每次只能在同一时间段做一份工作，例如：选择工作1，则在1~4时间段内不能做其他工作。问怎么选择工作时工作收益最大化？

（图来源于B站作者：正月点灯笼）

不难看出
如果要选择工作8，则收益为4，但是只能选择编号为6以前的工作，
如果不选择工作8，则无收益，但是可以选择编号为7以前的工作。

这就是动态分配的核心思想：选和不选

（+代表选择，-代表不选择，）
若继续细化下去，opt（6）就会分为选择：opt（2）+V6和不选择opt（5），
其中opt(5)就和我们选择opt（8）时计算的opt（5）重复计算，所以要存储起来。
用一个数组即可！

每一个结点在选择的时候，比较2种方案取最大值，就是这个结点的最优方案。

我们先算每个任务如果选择，它前面最近可选择的任务
不难从图中看出：

i	pre（i）
1	0
2	0
3	0
4	1
5	0
6	2
7	3
8	5

（i：工作编号，pre(i)：若选择编号为i的工作，则工作i之前能选择的最近工作）
例如：
选择工作7，时间为6~11，同一时间只能做一个工作，所以最近只能选择时间6之前的工作，即最近结束的是工作3。

根据这个思路，代码如下

public class Main {
	public static void main(String[] args) {
		int n = 8;	//机器人个数
		int[] pre = {0,0,0,0,1,0,2,3,5};	//选择这个工作之后前驱最近工作下标
		int[] profit = {5,1,8,4,6,3,2,4};	//工作收益
		int opt[] = new int[n+1];
		
		opt[0]=0;
		
		for(int i=1;i<opt.length;i++){
			opt[i]=Math.max(opt[i-1], opt[pre[i]]+profit[i-1]);	//比较2种方案，选择和不选择，取收益最大的方案
		}
		
		for(int i=1;i<n+1;i++){
			System.out.println(opt[i]);
		}
	}
}

运行输出

即为每个结点的最佳方案。
对于这个题目，则就是根节点的最佳方案，在数组中就是最后一个计算出来的，在数组的最后，即为13

感谢

笔者也为初学者，感谢Bilibili作者正月点灯笼，从他的教学中学习而来。
如有不足和错误，欢迎指正！