排列组合c的算法
排列组合C是指在n个元素中选取k个元素的组合数。 C(n,k)表示的是从n个元素当中选取k个元素的不同组合数目。
算法实现
1. 暴力枚举法
这种方法很简单直接，就是从n个元素中选取k个元素，假如我们已经选了其中的一个元素，那么显然就是要从剩下的n-1个元素中再选取k-1个元素，因此，排列组合c的公式就是：C(n,k) = C(n-1,k-1) + C(n-1,k)。
具体实现可以用递归来实现，代码如下：
public static int combination(int n, int k){
    if(k==0 || k==n){
        return 1;
    }else{
        return combination(n-1,k-1) + combination(n-1,k);
    }
}
2. 动态规划
动态规划是一个通用的算法，它可以用来求解具有一定规律的优化问题。对于排列组合C问题，我们可以使用动态规划来实现，其中状态转移方程为： dp[i][j] = dp[i-1][j] + dp[i-1][j-1]。
其中dp[i][j]表示从i个元素中选取j个元素的方案数。因为一个元素只能选取一次，因此当i>j时，dp[i][j] = dp[i-1][j]，即从i-1个元素中选取j个元素的方案数加上不选i个元素的方案数。当i=j时，dp[i][j] = 1。当j=0时，dp[i][j] = 1。边界条件非常容易理解。
typec转dp实现代码如下：
public static int combination(int n, int k) {
    int[][] dp = new int[n+1][k+1];
    for(int i=0; i<=n; i++){
        dp[i][0] = 1;
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=Math.min(i,k); j++){
            if(i==j){
                dp[i][j] = 1;
            }else{
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
            }
        }
    }
    return dp[n][k];
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。