puzzle - 可能的组合数

Question

如果我知道，变量 a,b,c,d,e 有多少可能的组合:

a+b+c+d+e = 500

并且它们都是整数且 >= 0，所以我知道它们是有限的。

Answer 1

@Torlack、@Jason Cohen:递归在这里是个坏主意，因为存在“重叠的子问题”。即，如果您选择 a如 1和 b如 2 ，那么你还有 3 个变量，加起来应该是 497；你通过选择 a 来解决相同的子问题如 2和 b如 1 . (这种巧合的数量随着数字的增长而爆炸式增长。)

解决此类问题的传统方法是 dynamic programming :自下而上地建立一个子问题的解决方案的表格(从“1个变量的多少组合加起来等于0？”开始)然后通过迭代建立(“n个变量的多少组合加起来”的解决方案到 k？”是“n-1 个变量的多少组合加起来等于 j？”的解的总和，其中 0 <= j <= k)。

public static long getCombos( int n, int sum ) {
  // tab[i][j] is how many combinations of (i+1) vars add up to j
  long[][] tab = new long[n][sum+1];
  // # of combos of 1 var for any sum is 1
  for( int j=0; j < tab[0].length; ++j ) {
    tab[0][j] = 1;
  }
  for( int i=1; i < tab.length; ++i ) {
    for( int j=0; j < tab[i].length; ++j ) {
      // # combos of (i+1) vars adding up to j is the sum of the #
      // of combos of i vars adding up to k, for all 0 <= k <= j
      // (choosing i vars forces the choice of the (i+1)st).
      tab[i][j] = 0;
      for( int k=0; k <= j; ++k ) {
        tab[i][j] += tab[i-1][k];
      }
    }
  }
  return tab[n-1][sum];
}

$ time java Combos
2656615626

真实 0m0.151s
用户 0m0.120s
系统 0m0.012s