Dynamic programming

• Optimal substructure: to the n layer can be obtained by summing the methods of the n-2 layer and the n-1 layer
• Boundary conditions: N<=3 method =N
• State transition equation: F (n)= F (n-2)+ F (n-1)

Direct recursion:

function fn(n){
	if(n<=3) return n;
	return fn(n-2)+fn(n-1);
}
Copy the code

This will time out

So we need to save the intermediate values, two at a time:

function fn(n){
	if(n<=3) return n;
	let i=4,x=3,y=2,r=0;
	while(i<=n){
		r=x+y;
		y=x;
		x=r;
		i++
	}
	return r;
}
Copy the code