真的尬留储，2020年藍(lán)橋杯模擬賽忘了，搞了幾把lol 上個(gè)廁所董虱，同學(xué)提醒時(shí)間不多了扼鞋，唯一一道比較有意思的題目申鱼，放下思路愤诱。
小明想知道，滿足以下條件的正整數(shù)序列的數(shù)量：
第一項(xiàng)為 n捐友；
第二項(xiàng)不超過(guò) n淫半；
從第三項(xiàng)開(kāi)始，每一項(xiàng)小于前兩項(xiàng)的差的絕對(duì)值匣砖。
? 請(qǐng)計(jì)算科吭，對(duì)于給定的 n，有多少種滿足條件的序列猴鲫。
思路对人，本質(zhì)上是求一個(gè)遞歸式，比如數(shù)字是n,那就是求(n,1)(n,2)等等拂共。然后不斷遞歸牺弄。但這題直接遞歸做，我估計(jì)時(shí)間很長(zhǎng)宜狐，所以考慮動(dòng)態(tài)規(guī)劃势告。把中間結(jié)果保存下來(lái)蛇捌。考慮一個(gè)n*n的二維矩陣咱台，n的答案分布就是填滿這個(gè)矩陣络拌，然后計(jì)算最后一行的和。（因?yàn)?1,n)在初始化序列之后也需要計(jì)算）回溺。
假設(shè)知道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;
}
