AcWing 2067. 走方格

在平面上有一些二维的点阵。

这些点的编号就像二维数组的编号一样，从上到下依次为第 1 至第 n 行，从左到右依次为第 1 至第 m 列，每一个点可以用行号和列号来表示。

现在有个人站在第 1 行第 1 列，要走到第 n 行第 m 列。

只能向右或者向下走。

注意，如果行号和列数都是偶数，不能走入这一格中。

问有多少种方案。

输入格式

输入一行包含两个整数 n,m。

输出格式

输出一个整数，表示答案。

数据范围

1≤n,m≤30

输入样例1：

3 4

输出样例1：

2

输入样例2：

6 6

输出样例2：

0

Code

dfs暴力

N  = 32
dx = [1,0]
dy = [0,1]
res = 0


def dfs(x,y):
    global res
    if x == n and y == m:
        res += 1

    for i in range(2):
        a = x + dx[i]
        b = y + dy[i]
        if 1<=a<=n and 1<=b<=m:
            if (a % 2 == 0) and (b % 2 == 0):
                continue
            dfs(a,b)


if __name__ == "__main__":
    n,m = map(int,input().split())

    dfs(1,1)
    print(res)

动态规划

N = 32
f = [[0] * N for _ in range(N)]


def DP():
    # 添加已知信息
    for i in range(1,n+1): f[i][1] = 1
    for j in range(1,m+1): f[1][j] = 1

    # 动态规划
    for i in range(2,n+1):
        for j in range(2,m+1):
            if (i % 2 == 0) and (j % 2 == 0):
                continue
            f[i][j] = f[i][j-1] + f[i-1][j]

    return f[n][m]


if __name__ == "__main__":
    n,m = map(int,input().split())

    print(DP())