题目链接

[蓝桥杯 2020 省 AB1] 走方格

题目描述

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

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

现在有个人站在第 $1$ 行第 $1$ 列，要走到第 $n$ 行第 $m$ 列。只能向右或者向下走。

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

问有多少种方案。

输入格式

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

输出格式

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

输入输出案例

输入

3 4

输出

2

数据范围

• $1\le n,m\le 30$

解法：动态规划

我们定义 $f(i,j)$ 为从点 $(1,1)$ 到点 $(i,j)$ 的方案数。

初始 $f(1,1)=1$。按照定义，最终返回的就是 $f(m,n)$（$m$ 行 $n$ 列的矩阵）。

考虑到点 $(i,j)$ 的方案数 $f(i,j)$：

• 如果 $i$ 和 $j$ 都是偶数，那么说明不能到达这个点，即到达这个点$(i,j)$ 的方案数为 $0$，$f(i,j)=0$；
• 否则，那么说明能到达这个点，即到达这个点$(i,j)$ 的方案数为 $f(i-1,j)+f(i,j-1)$，$f(i,j)=f(i-1,j)+f(i,j-1)$；

时间复杂度：$O(m\times n)$

C++代码：

#include <iostream>
#include <cstring>

using namespace std;
using LL = long long;

void solve(){
    int m, n;
    cin>>m>>n;
    
    int f[m + 5][n + 5];
    memset(f, 0, sizeof f);
    
    f[1][1] = 1;
    
    for(int i = 1;i <= m;i++){
        for(int j = 1;j <= n;j++){
            if((i & 1) == 0 && (j & 1) == 0){
                f[i][j] = 0;
            }
            else{
                f[i][j] += (f[i - 1][j] + f[i][j - 1]);
            }
        }
    }
    
    cout<<f[m][n]<<'\n';
}

int main(){
    int t = 1;
    while(t--)
    {
        solve();
    }
    
    return 0;
}

Java代码：

import java.util.*;
import java.io.*;

public class Main{
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	
	public static void main(String[] args) throws Exception 
	{
		String[] str = in.readLine().split(" ");
		int m = Integer.parseInt(str[0]);
		int n = Integer.parseInt(str[1]);
		
		int[][] f = new int[m + 5][n + 5];
		f[1][1] = 1;
		for(int i = 1;i <= m;i++) 
		{
			for(int j = 1;j <= n;j++) {
				if((i % 2 == 0) && (j % 2 == 0)) {
					f[i][j] = 0;
				}
				else {
					f[i][j] += (f[i - 1][j] + f[i][j - 1]);
				}
			}
		}
		
		System.out.println(f[m][n]);
	}
}