序列计数

2020.3 蓝桥杯模拟赛的一题
坑货，此题无法用dp，因为不管你怎么调整i和j的循环顺序，都会发现需要用到的状态没有被计算到。
能用记忆化搜索并不等价于能用dp，但是反之能用dp一定可以写成记忆化

记搜

#include<iostream>
using namespace std;

const int N = 1010, mod = 10000;

int f[N][N], st[N][N];
int n;

int dfs(int i, int j){
    if(j <= 0) return 0;
    if(st[i][j]) return f[i][j];
    f[i][j] = 1;
    st[i][j] = 1;
    for(int k = 1; k < abs(i - j); k ++) f[i][j] = (f[i][j] + dfs(j, k)) % mod;
    return f[i][j];
}

int main(){
    cin >> n;
    int res = 0;   
    for(int i = 1; i <= n; i ++) res = （res + dfs(n, i)) % mod;
    cout << res;
    return 0;
}

还是记搜

这边是把状态转移矩阵的一维的改成前缀和了。

#include<iostream>
using namespace std;

const int N = 1010, mod = 10000;

int f[N][N], st[N][N];
int n;

int dfs(int i, int j){
    if(j <= 0) return 0;
    if(st[i][j]) return f[i][j];
    f[i][j] = 1;
    st[i][j] = 1;
    f[i][j] = (f[i][j] + dfs(i, j - 1) + dfs(j, abs(i - j) - 1)) % mod;
    return f[i][j];
}

int main(){
    cin >> n;
    cout << dfs(n, n);
    return 0;
}