用于计算组合数的递归方法

Question

这是一个java代码,以递归方式计算特定硬币的支付数量(例如,1,2,5,20,50等).我试图找出它是如何工作但似乎无法得到它.有人可以这么善良并解释代码背后的数学和逻辑以及这种递归是如何工作的吗？我真的很感激.

    // Returns the count of ways we can sum  S[0...m-1] coins to get sum n
int count( int S[], int m, int n ){

    // If n is 0 then there is 1 solution (do not include any coin)
    if (n == 0)
        return 1;

    // If n is less than 0 then no solution exists
    if (n < 0)
        return 0;

    // If there are no coins and n is greater than 0, then no solution exist
    if (m <=0 && n >= 1)
        return 0;

    // count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}

Answer 1

该方法的工作方式如下:

1. 第一个语句是当前递归的停止条件(对于所有情况都没有这些语句,那么最终会出现一个无限循环,最终以StackOverFlow结尾)

2. 最后一行是计算发生的地方.每个语句都通过以下方式将问题缩小为更小的块:

   • count( S, m - 1, n )减少m-1在下次递归调用中排除最后一枚硬币的硬币数量()
   • count( S, m, n-S[m-1]) 使用数组中的最后一枚硬币,减少该硬币值所需的总和

考虑这个小例子:

S[] = {1,2)    // We have a 1 and 2 cent coin
m   = S.length // Consider all possibilities  ( = 2)
n   = 3        // How many ways can we make 3c
               // Obviously with: 1x1c + 1x2c
               //            and: 3x1c

作为树的递归; left branch = count( S, m - 1, n ),right branch = count( S, m, n-S[m-1]):

                                  m=2;n=3
                                 /        \
                          m=1;n=3          m=2;n=1
                         /       \       /     \
                  m=0;n=3    m=1;n=2   m=1;n=1  m=2;n=-1
                            /     \     /     \
                     m=0;n=2  m=1;n=1 m=0;n=1  m=1;n=0
                             /     \
                       m=0;n=1   m=1;n=0

此递归可以被认为是此树的预先遍历.

然后,如果您考虑了找到解决方案的方法的条件.所以在n = 0的叶节点处.

每一个都是这样的:

第一解决方案

1. m = 1; n = 3 - 排除最后一枚硬币(2c)
2. m = 1; n = 2 - 使用此硬币(1c)并减少1
3. m = 1; n = 1 - 使用此硬币(1c)并减少1
4. m = 1; n = 0 - 使用此硬币(1c)并减少1
5. n = 0 - 解决方案(3x1c)

二解决方案

1. m = 2; n = 1 - 使用此硬币(2c)并减少2
2. m = 1; n = 1 - 排除最后一枚硬币(2c)
3. m = 1; n = 0 - 使用此硬币(1c)并减少1
4. n = 0 - 解决方案(1x2c + 1x2c)

在每个节点返回一个值 - 0(无解)或1(解决方案) - 添加到找到的解的总数.一旦递归结束,返回该最终值并且是解决方案的数量.

一些额外的说明:

• 这段代码只考虑m数组中的第一个硬币,S以便考虑初始调用该方法所需的所有可能方法m == S.length
• 假设每枚硬币可以多次使用

使用print语句修改代码以查看递归:

public static void main(String[] args){
    int[] coins = new int[]{1,2};
    System.out.println("Final Count = " + count(coins, coins.length, 3, ""));
}

public static int calls = 0;

public static int count( int S[], int m, int n , String from){
    calls++;
    System.out.print("Call#" + calls + ": " + from + "; m = " + m + "; n = " + n);

    // If n is 0 then there is 1 solution (do not include any coin)
    if (n == 0)
    {
        System.out.println(" - Solution Found");
        return 1;
    }

    // If n is less than 0 then no solution exists
    if (n < 0)
    {
        System.out.println(" - No Solution Found n < 0");
        return 0;
    }

    // If there are no coins and n is greater than 0, then no solution exist
    if (m <=0 && n >= 1)
    {
        System.out.println(" - No Solution Found (other Case)");
        return 0;
    }

    System.out.println();
    // count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n , from + "E" ) + count( S, m, n-S[m-1], from + "I" );
}