题目描述

算法1

(爆搜) $\mathcal O(2 ^ {m + n})$

直接从 $(1, 1)$ 开搜，每搜到 $(n, m)$ 一次，ans ++一次。
最后输出ans即可。

时间复杂度

指数级别，玄学复杂度。
但说实话我没想到会TLE。。wtcl

$C$ 代码

#include <stdio.h>

int n, m;
int ans;

void dfs(int x, int y)        // 搜索 (x, y)
{
    if (x & 1 || y & 1)       // 如果至少存在一个点是奇数，那么搜索该点，否则跳过
    {
        if (x == n && y == m) // 如果搜到点 (n, m) 了
        {
            ans ++ ;          // ans ++ 并返回
            return ;
        }
        if (x < n) dfs(x + 1, y); // 如果 x 不到 n，那么搜 (x + 1, y)
        if (y < m) dfs(x, y + 1); // 如果 y 不到 m，那么搜 (x, y + 1)
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    dfs(1, 1);           // 从点 (1, 1) 开始搜索
    printf("%d\n", ans);
    return 0;
}

算法2

(记忆化搜索) $\mathcal O(nm)$

爆搜T了，改成记忆化搜索就好啦~
注意到数据范围不大，可以忽略爆栈的风险~

时间复杂度

每个点只会被处理一次，一共有 $n + m$ 个点，所以总时间复杂度为 $\mathcal O(nm)$

C 代码

#include <stdio.h>

int n, m;
int f[31][31];        // 记忆化数组

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]; // 最后返回 f[x][y] 即可。如果 x, y 都是偶数，那么 f[x][y] 就没被处理过，必然为 0，可以不特判。
}

int main()
{
    scanf("%d%d", &n, &m);
    f[n][m] = n & 1 || m & 1;  // 这里要特判下 n, m 是否都为偶数
    printf("%d\n", dfs(1, 1));
    return 0;
}

算法3

(动态规划) $\mathcal O(nm)$

f[i][j] 表示从点 $(1, 1)$ 走到点 $(n, m)$ 的方案数。
如果 $i, j$ 都是偶数，那么特判为 $0$。
否则只能从上边或者左边转移过来，即f[i][j] = f[i - 1][j] + f[i][j - 1]
边界情况：f[i][1] = f[1][j] = 1

时间复杂度

$\mathcal O(nm)$

C代码

#include <stdio.h>

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

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) f[i][1] = 1; // 边界 f[i][1] 特判为 1
    for (int j = 1; j <= m; j ++ ) f[1][j] = 1; // 边界 f[1][j] 特判为 1
    for (int i = 2; i <= n; i ++ )              // 枚举 i
        for (int j = 2; j <= m; j ++ )          // 枚举 j
            if (i & 1 || j & 1)                 // 如果 i, j 中有一个是奇数
                f[i][j] = f[i - 1][j] + f[i][j - 1]; // 那么进行状态转移
    printf("%d\n", f[n][m]); // 转移后 f[n][m] 即为答案
    return 0;
}

补点东西。

根据上面的状态转移方程，在计算 f[i][j] 时，只用到了 f[i - 1][j] 和 f[i][j - 1]，这使我们可以压掉第一维空间。

空间复杂度

$O(m)$。

注意问题关于 $n, m$ 对称，那么若 $m$ 远大于 $n$，可以将 $n, m$ 交换，这不影响答案。于是也有空间复杂度为 $\min(n, m)$ 的算法。

C代码

#include <stdio.h>

int n, m;
int f[31];

int main()
{
    scanf("%d%d", &n, &m);
    for (int j = 1; j <= m; j ++ ) f[j] = (j & 1);
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            if (i & 1 || j & 1)
                f[j] = f[j] + f[j - 1];
            else
                f[j] = 0;
    printf("%d\n", f[m]);
    return 0;
}