#include <iostream>
using namespace std;
const int mod = 1e9 + 7;
int dp_1[10000],dp_2[10000];
int main()
{
    int n;
    cin >> n;
    dp_1[0] = 10;
    for (int i = 1;i<n;i++)
    {
        dp_1[i] = dp_1[i - 1] * 10;
    }
    dp_2[0] = dp_1[0];
    dp_2[1] = dp_1[1];
    for (int i = 2;i<n;i++)
    {
        dp_2[i] = (dp_1[i] + dp_2[i - 2])%mod;
        for (int j = 1;j<n-1;i++)
        {
            dp_2[i] += (dp_2[j] * dp_2[i - j - 1])%mod;
        }
        dp_2[i] %= mod;
    }
    cout << dp_2[n - 1];
}
第二题答案。
不能检测了，不敢说对。但思想没毛病。dp_1表示只有字符的情况。dp_2[i]要加上dp_2[i-2],
是考虑括号。最后的循环是考虑加号。