AcWing 2067. 走方格
原题链接
简单
作者:
不可思议_3
,
2024-03-13 21:01:36
,
所有人可见
,
阅读 11
递归直接超时,没想到动态规划
#include<bits/stdc++.h>
using namespace std;
int n,m,res;
int a[50][50];
void dfs(int x,int y){
if(x%2 == 0 && y%2 == 0 || x>m && y<n || x<m && y>n){
return;
}
if(x == m && y == n){
res++;
return;
}
if(!a[x][y] ){
a[x][y] = 1;
dfs(x+1,y);
dfs(x,y+1);
a[x][y] = 0;
}
}
int main(){
cin>>n>>m;
dfs(1,1);
cout<<res<<endl;
return 0;
}
动态规划
#include<iostream>
using namespace std;
int n,m;
int dp[35][35];
int main()
{
cin>>n>>m;
dp[1][1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(i%2!=0||j%2!=0)
dp[i][j]+=dp[i-1][j]+dp[i][j-1];
cout<<dp[n][m];
}