201301 JAVA题目2-3级（用递归和排列组合）

本文主要是介绍201301 JAVA题目2-3级（用递归和排列组合），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

链接：https://www.nowcoder.com/questionTerminal/e2a22f0305eb4f2f9846e7d644dba09b

请编写一个函数（允许增加子函数），计算n×m个的棋盘格子（正为横向的格子数，米为竖向的格子数）沿着各自边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。

输入描述

输入俩个正整数

输出描述

输出结果

示例1

输入
2
2

输出
6

解题思路1：

使用递归的思想，将（0, 0）作为终点，将（m, n）作为起点，然后从起点一直递归走。
首先，向右走一步为（m , n-1）然后向下走为（m-1, n），最终无论 m 和 n 谁为0了，那么就只有棋盘边缘一条路可以走了。这也是递归的终止条件。

解题代码：

#include <iostream>
using namespace std;int Count(int m, int n) {if (m == 0 || n == 0) {return 1;}return Count(m, n - 1) + Count(m - 1, n);
}int main() {int m, n;cin >> m >> n; cout << func(m, n) << endl;return 0;

解题思路2：

这个题目是典型的概率论 C 排列问题。每次要到达终点始终会走 m 行，n 列，所以这个排列组合是对顺序没有要求的 C 排列问题，也就是 C(m, m+n) 问题。

解题代码：

#include <iostream>
using namespace std;int main(){int m, n;cin >> m >> n;int C_up = 1;int C_down = 1;for (int i = 0; i<n; i++){C_up *= (m + n) - i;C_down *= i + 1;}cout << C_up / C_down << endl;return 0;
}