tips:

n x m 的棋盘的边界,意味着有 n+1 x m+1个点

动态规划

• 状态转移方程为:

f[i][j] = f[i-1][j] + f[i][j-1]

• 需要注意的是在边界的点是都为1

import java.util.Scanner;
public class Main{
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int [][]vis = new int [n+1][m+1];
        for(int i =0 ;i<n+1;i++){
            for(int j = 0;j<m+1;j++){
                int up = i-1<0?0:vis[i-1][j];
                int left = j-1<0?0:vis[i][j-1];
                if(i == 0 && j==0) vis[i][j] = up + left;
                else if(i == 0 || j==0) vis[i][j] = 1;
                else vis[i][j] = up + left;
//                 System.out.println("i: "+i+" j: "+j+" vis: "+vis[i][j]);
            }
        }
        System.out.println(vis[n][m]);
        
    }
}

DFS

• 深度优先遍历/记忆化搜索

import java.util.Scanner;
public class Main{
    public static int ans = 0;
    public static void dfs(int x,int y, int [][]vis){
        int n = vis.length;
        int m = vis[0].length;
        if(x == n-1 && y == m-1 ){
            ans++;
            return;
        }
        int [][]dir = {{0,1},{1,0}};
        for(int i = 0;i<2;i++){
            if(vis[x][y]==0){
                vis[x][y] =1 ;
                int xx = x + dir[i][0];
                int yy = y + dir[i][1];
                if(xx<n && xx>=0 && yy < m && yy>= 0 && vis[xx][yy]==0){
                    dfs(xx,yy,vis);
                }
            }
            vis[x][y] = 0;
        }
    }
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int [][]vis = new int [n+1][m+1];
         dfs(0,0,vis); // dfs
         System.out.println(ans);     
    }
}