java - Java中的递归nCr组合

Question

我有一个任务是创建两个计算 nCr 的递归方法（在 Java 中）。我写的第一个方法是使用帕斯卡三角形。它有效，帕斯卡三角形非常棒。

但是现在我遇到了一个问题，因为我无法思考/找到任何其他递归解决方案，两个编写我的第二个计算 nCr 的方法。我曾尝试使用/编写一种基于找出阶乘的方法，但是当我使用大数字时该方法会破裂。

有人可以给我一些关于其他递归计算 nCr 方法的提示、建议和建议吗？

非常感谢！

Answer 1

我可以提供用 C++ 创建的问题的解决方案。

#include <iostream>
#include <cstring>
int dp[100][100];
int choose(int a, int b)
{
    if(a < b) return 0;
    if(dp[a][b] != -1) return dp[a][b];
    if(b == 0) return 1;
    if(b == 1) return a;
    dp[a][b] = (choose(a - 1, b) + choose(a - 1, b - 1));
    return dp[a][b];
}
int main()
{
    memset(dp, -1, sizeof(dp));
    return 0;
}