P8707 [蓝桥杯 2020 省 AB1] 走方格

原题链接：[蓝桥杯 2020 省 AB1] 走方格 - 洛谷

目录

1.题目描述

2.思路分析

3.代码实现

---

1.题目描述

2.思路分析

题目大意：现在有个人站在第 1 行第 1 列，要走到第 i 行第 j 列（每次只能向右或者向下走），如果行号和列号都是偶数，不能走入这一格中。问有多少种方案？

dp。

设dp[i][j]表示走到第 i 行第 j 列时的方案数。

初始状态：dp[1][j]=dp[i][1]=0 （因为每次只能向右或向下走，所以如果从（1,1）到第一行上所有的点的方案，只有水平向右走这一种。从（1,1）到第一列上所有点的方案，只有竖直向下这一种）。

状态转移方程: dp[i][j]=dp[i-1][j]+dp[i][j-1]

因为不能走入行号和列号均为偶数的格子，所以当行号和列号均为偶数（也就是i%2==0&&j%2==0）时，dp[i][j]=0。

因为我们已经考虑过了从（1,1）到第一行或者到第一列的情况，所以循环枚举时我们从（2,2）开始。

求解目标：dp[n][m]

3.代码实现

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
ll dp[40][40];int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n, m; cin >> n >> m;for (int i = 1; i <= n; i++) dp[i][1] = 1;for (int j = 1; j <= m; j++) dp[1][j] = 1;for (int i = 2; i <= n; i++) {for (int j = 2; j <= m; j++) {if (i % 2 == 0 && j % 2 == 0) dp[i][j] = 0;else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}cout << dp[n][m] << endl;return 0;
}