小明想知道，满足以下条件的正整数序列的数量：
 1. 第一项为 n；
 2. 第二项不超过 n；
 3. 从第三项开始，每一项小于前两项的差的绝对值。
 请计算，对于给定的 n，有多少种满足条件的序列。

dfs+记忆化 

import java.util.*;
import java.math.*;
public class Main 
{
    static Scanner input = new Scanner(System.in);
    public static int n = input.nextInt();
    public static long ans=0;
    public static int p=1;
    public static int a[] = new int[100];
    public static long b[][] = new long[1000][1000];
    public static void main(String[] args) 
    {
        a[0] = n;
        for(int i=1;i<=n;i++)
        {
            a[p] = i;
            ans++;
            dfs(Math.abs(a[0]-a[1]));
        }
        System.out.println(ans%10000);
    }
    public static void dfs(int x)
    {
        for(int i=1;i<x;i++)
        {
            p++;
            a[p] = i;
            ans++;
            long aa=ans;
            if(b[a[p-1]][a[p]]!=0)
            	ans+=b[a[p-1]][a[p]];
            else
            	{
            	dfs(Math.abs(a[p]-a[p-1]));
            	b[a[p-1]][a[p]] = (ans-aa)%10000;
            	}
            a[p] = 0;
            p--;
        }
    }
}