第11回ブルーブリッジカップ校内試合/校内選抜試合(2020年)I題シーケンス

シーケンス#シーケンス#
問題の説明
明ちゃんは、以下の条件を満たす正の整数シーケンスの数を知りたいです:1.第1項はnである.　　2. 第2項はnを超えない.　　3. 3番目の項目から、各項目は前の2つの項目の差の絶対値より小さい.与えられたnに対して、条件を満たすシーケンスがどれだけあるかを計算してください.
入力フォーマット
入力行には整数nが含まれます.
出力フォーマット
答えを表す整数を出力します.答えは大きいかもしれませんが、答えを10000で割った余りを出力してください.
サンプル入力
4
サンプル出力
7
サンプルの説明は以下の条件を満たすシーケンスである:4 1 4 1 1 4 1 4 2 4 4 2 1 4 4 4 4 4評価用例の規模と約束20%の評価用例に対して、1<=n<=5;50%の評価例について、1<=n<=10;80%の評価例について、1<=n<=100;すべての評価例について、1<=n<=1000である.
タイトルから分かるように,3位で利用可能な数は上位2位にのみ関係している.初期1位はnであった.2位の範囲は1~n.nが第1位、mが第2位の可能なシーケンスをT(n,m)で表すと、nに対する解はT(n,1)+T(n,2)+...+T(n,n)であり、T(n,m)に対する解はT(n,m)=1+T(m,1)+T(m,2)+...+T(m,|n-m|-1)である.例えば6 3から始まるシーケンス、T(6,3)=1+T(3,1)+T(3,2).だから以上の結論から解が得られる.以下はJavaコードのみ参照

import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int n = sc.nextInt();
		int ans[][] = new int[n + 1][n + 1];
		int jg = 0;
		for (int i = 1; i <= n; i++) {
			jg += jie(ans, n, i);
		}
		System.out.println(jg%10000);
	}

	private static int jie(int[][] ans, int n, int m) {
		if (ans[n][m] != 0) {
			return ans[n][m];
		}
		int te = 1;
		for (int i = 1; i < Math.abs(n - m); i++) {
			te = (te + jie(ans, m, i)) % 10000;
		}
		return ans[n][m] = te;
	}
}

1000の結果をテストするのにかかる時間は約1300msで、通常Javaコードは2秒かかり、プログラムはタイムアウトしません.