蓝桥杯校内模拟赛

真的尬，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;

}