这道题如果用递归，则略显俗了，而且空间复杂度太高。

最近练了很多动态规划的题，这一题就特别适合：

package main

import (
	"fmt"
)

func main() {
	a := 0
	fmt.Scan(&a)

	dp := []int{0, 1, 1}
	for i := 3; i <= a; i++ {
		dp = append(dp, dp[i-1]+dp[i-2])
	}
	fmt.Printf("%d", dp[a])
}