AcWing 2067. 走方格
原题链接
简单
作者:
stc
,
2024-03-01 11:30:34
,
所有人可见
,
阅读 23
dfs O(2^min(n,m)) 超时
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
int cnt;
int dx[2]={0,1},dy[2]={1,0};
void dfs(int x,int y){
if(x == n && y == m) {
cnt ++;
return;
}
if(x == n+1 || y == m+1) return ;
for(int i=0;i<2;i++){
int tx = x + dx[i], ty = y + dy[i];
if(tx%2==0 && ty%2==0) continue;
dfs(tx,ty);
}
}
int main()
{
cin >> n >> m;
dfs(1,1);
cout<<cnt<<endl;
return 0;
}
dp O(nm)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 35;
int n,m;
int f[N][N]; // dp[i][j]表示从(1,1)到(i,j)的方案数
// dp[i][j] = max(dp[i][j-1]+1,dp[i-1][j]+1);
int main()
{
cin>>n>>m;
f[1][1] = 1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i == 1 && j ==1) continue;
if(i%2 == 0 && j%2 ==0){
f[i][j] = 0;
continue;
}
f[i][j] = f[i-1][j] + f[i][j-1];
}
}
cout<<f[n][m]<<endl;
return 0;
}