Question

Free Pascal 深度优先搜索的题目

有N阶台阶,一次可以上1阶或2阶,一共有多少种走法,并输出

Answer 1

var
	m,num:longint;

procedure next(step,n:integer;var m,num:longint); 
	{step步数，n累加总级数，m给定级数，num路径数}
begin
	if step>=0 then
	begin
		if n=m then inc(num);
		if n<m then next(step-1,n+1,m,num); 
		if n<m-1 then next(step-1,n+2,m,num); 
	end;
end;
begin
	readln(m);
	num:=0;
	next(m,0,m,num);
	writeln(num);
end.	

递归解法。踏步台阶数在35以内速度非常快。
答案实际上就是菲波纳稧级数

追答

不用f(n)=f(n-1)+f(n-2)这个递推公式，这是复杂度最小的算法。
由此也可以推广到一步走一级、二级、三级甚至更多级的情况！