走方格的方案数

题目描述

请计算 $n*m$ 的棋盘格子（$n$ 为横向的格子数，$m$ 为竖向的格子数）沿着各自边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。

递归思想

从 $(m, n)—>(0, 0)$ 就只有两种走法：往右走一步：$f(m, n - 1)—>(0, 0)$ 或 往下走一步：$f(m - 1, n)—>(0, 0)$递归通式：$f(m, n) = f(m, n - 1) + f(m - 1, n)$当走到边界，即 $f(0,x)$ 或 $f(x,0)$ 都只能走一条直线了递归终止条件：$n = 0 || m = 0$

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String arr[];
        int n,m;
        while (in.hasNext()) { 
            String s = in.nextLine();
            arr = s.split(" ");
            n = Integer.parseInt(arr[0]);
            m = Integer.parseInt(arr[1]);
            System.out.println(getStep(n,m));
        }
    }
    public static int getStep(int n,int m){
        if(n == 0 || m == 0){ //递归终止条件
            return 1;
        }
        return getStep(n-1,m)+getStep(n,m-1); //递归通式
    }
}

原题链接 华为机试：走方格的方案数