小明想知道，满足以下条件的正整数序列的数量：
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--;
}
}
}
