【问题描述】 小明想知道，满足以下条件的正整数序列的数量： 1. 第一项为 n； 2. 第二项不超过 n； 3. 从第三项开始，每一项小于前两项的差的绝对值。 请计算，对于给定的 n，有多少种满足条件的序列。 【输入格式】 输入一行包含一个整数 n。 【输出格式】 输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。 【样例输入】 4 【样例输出】 7 【样例说明】 以下是满足条件的序列： 4 1 4 1 1 4 1 2 4 2 4 2 1 4 3 4 4 【评测用例规模与约定】 对于 20% 的评测用例，1 <= n <= 5； 对于 50% 的评测用例，1 <= n <= 10； 对于 80% 的评测用例，1 <= n <= 100； 对于所有评测用例，1 <= n <= 1000。
思路：递归
程序1：（严重超时，待修改，可以用动态规划的方法，将中间计算结果存储从而减少重复计算）
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include<math.h> using namespace std; int sum=0; void Search(int Former, int Interval) { int i; sum++; for (i = 1; i < Interval; i++) { if (abs(i - Former) < 2) sum++; else Search(i, abs(i - Former)); } } int main() { int n, i; cin >> n; Search(n, n); if (sum > 10000) printf("%d\n", sum % 10000); else printf("%d\n", sum); return 0; }程序2（修改后的程序）
