AcWing 2067. 走方格
原题链接
简单
作者:
暂时换个名字
,
2021-01-26 17:00:19
,
所有人可见
,
阅读 282
import java.util.Scanner;
public class Main {
static int n,m;
static int[][] biao;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n=sc.nextInt();m=sc.nextInt();biao=new int[n+1][m+1];
if(n%2!=0||m%2!=0)
//bfs(1,1);System.out.println(biao[1][1]);
dp();System.out.println(biao[n][m]);
}
public static int bfs(int x,int y) {//用记忆深搜来做
if(x>=n&&y>=m)return 1;
if(biao[x][y]!=0)return biao[x][y];
int res=0;
if(y+1<=m&&(x%2!=0||(y+1)%2!=0))res+=bfs(x,y+1);
if(x+1<=n&&((x+1)%2!=0||y%2!=0))res+=bfs(x+1,y);
return biao[x][y]=res;
}
public static void dp() {//dp来做
for(int i=1;i<=n;i++) {
biao[i][1]=1;
for(int j=2;j<=m;j++) {
if(i%2==0&&j%2==0)biao[i][j]=0;
else biao[i][j]=biao[i-1][j]+biao[i][j-1];
}
}
}
}