题目描述
在平面上有一些二维的点阵。这些点的编号就像二维数组的编号一样，从上到下依次为第 1 至第 n 行，从左到右依次为第 1 至第 m 列，每一个点可以用行号和列号来表示。现在有个人站在第 1 行第 1 列，要走到第 n 行第 m 列。只能向右或者向下走。问有多少种方案？
注意，如果行号和列数都是偶数，不能走入这一格中。
输入格式：
输入一行包含两个整数 nn，mm。
输入一行包含两个整数 nn，mm。
输出格式：
输出一个整数，表示答案。
输出一个整数，表示答案。
题解
经典的动态规划，只能从上面和左边进入状态。
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis));
using namespace std;
int dp[35][35];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
mem(dp, 0);
int m, n;
cin >> m >> n;
dp[1][1] = 1;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if((i & 1) == 0 && (j & 1) == 0){
continue;
}
dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
}
}
cout << dp[m][n] << endl;
return 0;
}
