Java中的递归nCr组合

Question

我有一个任务是创建两个计算nCr的递归方法(在Java中)。我写的第一个方法是使用Pascal三角形。很好，帕斯卡三角很棒。

但是现在我遇到了一个问题，因为我无法思考/找到任何其他递归解决方案，第二种方法是计算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;
}