真的尬，2020年蓝桥杯模拟赛忘了，搞了几把lol 上个厕所，同学提醒时间不多了，唯一一道比较有意思的题目，放下思路。
小明想知道，满足以下条件的正整数序列的数量：
第一项为 n；
第二项不超过 n；
从第三项开始，每一项小于前两项的差的绝对值。
请计算，对于给定的 n，有多少种满足条件的序列。
思路，本质上是求一个递归式，比如数字是n,那就是求(n,1)(n,2)等等。然后不断递归。但这题直接递归做，我估计时间很长，所以考虑动态规划。把中间结果保存下来。考虑一个n*n的二维矩阵，n的答案分布就是填满这个矩阵，然后计算最后一行的和。（因为(1,n)在初始化序列之后也需要计算）。
假设知道n-1的所有答案分布，那么n的答案就是(n,1) = 1+(1,n-2) ，(n,2) = 1+(1,n-3)等等，注意这些答案都在n-1的答案分布里。
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int main() {
int n;
cin >> n;
int** array = new int* [n+1];
for (int i = 0; i <= n; i++) {
array[i] = new int[n+1];
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
array[i][j] = 0;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
int temp = (int)abs(i - j);
for (int k = 1; k < temp; k++) {
array[i][j] += array[j][k];
}
array[i][j] += 1;
if (i != j) {
for (int k = 1; k < temp; k++) {
array[j][i] += array[i][k];
}
array[j][i] += 1;
}
}
}
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += array[n][i];
}
cout << sum;
}
