爆搜 10项测试过了9项,最后一项直接TLE

#include<iostream>
using namespace std;

int n,m;

int dfs(int x,int y)
{
    if(x > n || y > m || !(x & 1 || y & 1))  return 0;

    if(x == n && y == m)    return 1;

    return dfs(x+1,y) + dfs(x,y+1);
}

int main()
{
    scanf("%d%d",&n,&m);

    printf("%d",dfs(1,1));

    return 0;
}

记忆化搜索:省去重复部分来完成剪枝

#include<iostream>
using namespace std;

int n,m;
int f[32][32];

int dfs(int x,int y)
{
    if(x <= n && y <= m && (x & 1 || y & 1))
    {
        if(f[x][y]) return f[x][y];
        if(x == n && y == m)    return 1;
        f[x][y] += dfs(x + 1,y) + dfs(x,y + 1);
    }
    return f[x][y];
}

int main()
{
    scanf("%d%d",&n,&m);

    printf("%d",dfs(1,1));

    return 0;
}

线性DP

#include<iostream>
using namespace std;

int n,m;
int f[32][32];

int main()
{
    scanf("%d%d",&n,&m);

    f[1][0] = 1;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            if(i & 1 || j & 1)
                f[i][j] = f[i-1][j] + f[i][j-1];

    printf("%d",f[n][m]);
    return 0;
}