记忆化搜索

//
// Created by Genes on 2020/10/16.
//
// 走方格
// 记忆化搜索/dp

#include<iostream>

using namespace std;

const int N = 3e1 + 5;

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

int dfs(int x, int y) { //搜索点(x,y), 返回从(x,y)开始, 能到(n,m)的路径数量
    if (x & 1 || y & 1) {//不是偶数
        if (f[x][y]) return f[x][y];//如果该点已经被搜索过, 那么不再处理
        //否则说明没有搜过, 需要再搜索一遍
        if (x < n) f[x][y] += dfs(x + 1, y);
        if (y < m) f[x][y] += dfs(x, y + 1);
    }
    return f[x][y];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    f[n][m] = n & 1 || m & 1;
    cout << dfs(1, 1);
}

动态规划

//
// Created by Genes on 2020/10/16.
//
// 走方格, dp做法

#include<iostream>

using namespace std;

const int N = 3e1 + 5;

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

inline int solve() {
    cin >> n >> m;
    f[1][1] = 1;//边界
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) {
                continue;
            }
            if (!(i & 1 || j & 1)) {
                continue;
            }
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    cout << f[n][m] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}