dfs纯暴力做法

#include<iostream>
using namespace std;

const int N = 35;
int n, m, res;
int st[N][N];
int x[2] = {0, 1}, y[2] = {1, 0};

void dfs(int dx, int dy){
    if(dx > n || dy > m) return;
    if(dx == n && dy == m){
        res++;
        return;
    }
    for(int i = 0; i < 2; i++){
        int nx = dx + x[i], ny = dy + y[i];
        if(nx <= 0 || nx > n || ny <= 0 || ny > m || st[nx][ny]) continue;
        if(nx % 2 == 0 && ny % 2 == 0) continue;
        st[nx][ny] = 1;
        dfs(nx, ny);
        st[nx][ny] = 0;
    }
}

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

dfs + 记忆化搜索

#include<iostream>
using namespace std;

const int N = 35;
int n, m;
int f[N][N];//记忆化数组,此处代表从(i, j)开始，能到达终点的路径数量
int x[2] = {0, 1}, y[2] = {1, 0};

int dfs(int dx, int dy){//从(dx,dy)开始搜索，并返回从点(dx,dy)开始，能到达终点的路径数量
    if(f[dx][dy]) return f[dx][dy];
    for(int i = 0; i < 2; i++){
        int nx = dx + x[i], ny = dy + y[i];
        if(nx % 2 == 0 && ny % 2 == 0 || nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
        f[dx][dy] += dfs(nx, ny); 
    }
    return f[dx][dy];
}

int main(){
    cin >> n >> m;
    f[n][m] = 1;
    cout << dfs(1, 1) << endl;;
    return 0;
}

dp

#include<iostream>
using namespace std;

const int N = 35;
int n, m;
int dp[N][N];

int main(){
    cin >> n >> m;
    dp[1][1] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i % 2 == 0 && j % 2 == 0) continue;
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
        }
    }
    cout << dp[n][m];
    return 0;
}