试题 H: 走方格 C/C++ [递归、动态规划]两种方法

试题 H: 走方格
时间限制: 1.0s 内存限制: 256.0MB 本题总分：20 分
【问题描述】
在平面上有一些二维的点阵。 这些点的编号就像二维数组的编号一样，从上到下依次为第 1 至第 n 行， 从左到右依次为第 1 至第 m 列，每一个点可以用行号和列号来表示。 现在有个人站在第 1 行第 1 列，要走到第 n 行第 m 列。只能向右或者向下 走。
注意，如果行号和列数都是偶数，不能走入这一格中。
问有多少种方案。
【输入格式】 输入一行包含两个整数 n, m。
【输出格式】
输出一个整数，表示答案。
【样例输入】 3 4
【样例输出】 2
【样例输入】 6 6
【样例输出】 0
【评测用例规模与约定】 对于所有评测用例，1≤n≤30, 1≤m≤30。

第一种方法：递归求解：

//走方格---- 递归 ----做法// 

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;

int sum = 0;
int a[35][35];
int n,m;
void f(int x,int y);

int main()
{
	memset(a,0,sizeof(a));
	cin >> n >> m;
	f(1,1);
	cout << sum << endl;
	return 0;
 } 
 
 
void f(int x,int y)
{
	if(x % 2 == 0 && y % 2 == 0) return ;
	if(x == n && y == m)
	{
		sum ++;
		return ;
	}
	if(x != n) f(x + 1,y);
	if(y != m) f(x,y + 1);
 } 

关于递归：①先找到走出递归的条件，这里就是这两行代码↓

if(x % 2 == 0 && y % 2 == 0) return ;
	if(x == n && y == m)
	{
		sum ++;
		return ;
	}

②再写继续递归的条件

if(x != n) f(x + 1,y);
if(y != m) f(x,y + 1);

以下是自己的输入输出：

第二种方法：动态规划

//走方格---- 动态规划 ----做法// 

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;

int sum = 0;
int a[35][35];
int n,m;
void f(int x,int y);

int main()
{
	memset(a,0,sizeof(a));
	cin >> n >> m;
	f(1,1);
	cout << a[n][m] << endl;
	return 0;
 } 
 
 
void f(int x,int y)
{
	int i,j;
	for(i = 1;i <= n;i ++)
		a[i][1] = 1;
	for(j = 1;j <= m;j ++)
		a[1][j] = 1;
		
	for(i = 2;i <= n;i ++)
	{
		for(j = 2;j <= m;j ++)
		{
			if(i % 2 != 0 || j % 2 != 0)
			{
				a[i][j] = a[i-1][j] + a[i][j - 1];
			}
		}
	}
 } 

动态规划做法，注意i和j都是从2开始的，因为从1开始的话，数组其实是1<=i<=n行第一个元素都是1以及1<=j<=m第一列元素都是1，这样a[0][0] a[1][0] a[0][1]这三个都是0，如果i,j从一开始会受这些0的影响，但是这些0本来就不参与运算的。

以下是自己的输入输出：

这里对比了两种方法，可以很明显地感觉到，当输入的数字变大的时候，即当我输入29 29的时候，动态规划的速度要比递归的速度明显快很多！！所以参加蓝桥杯如果可以使用动态规划就尽量使用动态规划吧！！！！