--01
--楼梯有n阶台阶 上楼可以一步上一节 也可以一步上两节  多少种走法
--递归求解

function Way(n)
	local ans={}
	if n==1 then
		table.insert(ans,{1})
		return ans

	elseif n==2 then
		local tmp1={1,1}
		local tmp2={2}
		table.insert(ans,tmp1)
		table.insert(ans,tmp2)
		return ans

	else
		local ans1=Way(n-1)
		for i,v in pairs(ans1) do
			table.insert(ans1[i],1)
			table.insert(ans,ans1[i])
		end

		local ans2=Way(n-2)
		for i,v in pairs(ans2) do
			table.insert(ans2[i],2)
			table.insert(ans,ans2[i])
		end


		return ans
	end
end

ans=Way(4)
for i,v in pairs(ans) do
	print("solve"..i..":"..table.concat(ans[i],"-"))
end

--迭代求解

function Way(n)
	resultAll={}
	tempArr1={""}
	resultAll[1]=tempArr1
	tempArr2={" 1"}
	resultAll[2]=tempArr2

	for i=3,n+1 do
		resultAll[i]={}
		for j=1,#(resultAll[i-1]) do
			table.insert(resultAll[i],resultAll[i-1][j].." 1")

		end

		for j=1,#(resultAll[i-2]) do
			table.insert(resultAll[i],resultAll[i-2][j].." 2")
		end
	end

	for i=1,#resultAll[n+1] do
		print(resultAll[n+1][i])
	end
end

print("请输入阶层数")
ans=Way(5)