Java机试题：请计算n*m的棋盘格子，从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法。【动态规划（递推、递归、迭代）】

描述

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

思路

参考链接：https://www.nowcoder.com/questionTerminal/e2a22f0305eb4f2f9846e7d644dba09b 用递归来做，将右下角看做原点(0, 0)，左上角看做坐标(m, n)： 从(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(x, 0)或者f(0,x)都只有一条直路可走了，则结束循环条件如下： m == 0 || n == 0 , return 1;

import java.util.*;


public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextLine()){
           String[] nums =  sc.nextLine().split(" ");
           int n = Integer.valueOf(nums[0]);
           int m = Integer.valueOf(nums[1]);
           int sum = getNums(n,m);
           System.out.println(sum) ;
        }
 
    }
     
    // 动态规划，递归函数
     public static int getNums(int n,int m) {
         // 递归函数结束条件
         if( n ==0 || m == 0){
             return 1;
         } else {
　　　　　　　　// n,m的走法，等于 n-1,m与n,m -1相加
             return getNums(n - 1, m) + getNums(n, m -1);
         }
     }
}