本文共 983 字，大约阅读时间需要 3 分钟。

【问题描述】

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

这些点的编号就像二维数组的编号一样，从上到下依次为第 1 至第 n 行，

从左到右依次为第 1 至第 m 列，每一个点可以用行号和列号来表示。

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

走。

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

问有多少种方案。

法一：dfs+递归

#include 
   
    using namespace std;int a[40][40];int res = 0;int n;int m;bool rcheck(int y)//检查向右走是否越界{
   	if(y+1<=m)		return 1;	else		return 0;}bool dcheck(int x)//检查向下走是否越界{
   	if(x+1<=n)		return 1;	else		return 0;}bool ref(int x,int y)//检查此时是否为偶数点{
   	if(x%2==0&&y%2==0)	{
   		return 0;	}	else		return 1;}void dfs(int x,int y){
   	if(x==n&&y==m)	{
   		res++;	}	if(rcheck(y)&&ref(x,y+1))	{
   		dfs(x,y+1);	}	if(dcheck(x)&&ref(x+1,y))	{
   		dfs(x+1,y);	}}int main(){
   		int x = 1;	int y = 1;	cin>>n>>m;	dfs(x,y);		cout<
    
     <
    
   

法二：动态规划

找准状态转移方程：

#include 
   
    using namespace std;int main(){
       int n,m;    cin>>n>>m;    vector
    
     
       > dp(n+1,vector
      
       (m+1));//和定义二维数组是一样的，这里只不过使用vector容器定义二维    for(int i=1;i
      
     
    
   

转载地址：https://blog.csdn.net/xiangguang_fight/article/details/115707009 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！