0

我的程序计算 的整数分区n，它们具有k不同的分区元素，每个分区都小于或等于m。我怎样才能提高性能？我已经缓存了中间结果。

public long q(int n, int m, int k) {
    return q1(n, m, k, 0, 0, new HashMap());
}

private long q1(int n, int m, int k, int level, int last, Map<String, Long> cache) {
    if (n < 0) {
        return 0;
    }
    if (level + 1 == k) {
        if (n > m) {
            return 0;
        } else {
            return 1;
        }
    }
    int first = (level == 0) ? 1 : last + 1;
    long total = 0;
    for (int i = first; i <= Math.min(m, n / 2); i++) {
        last = i;
        if (n - i > 0 && last < n - i) {
            String key = n - i + "_" + level + 1 + "_" + last;
            Long fetched = cache.get(key);
            if (fetched == null) {
                fetched = q1(n - i, m, k, level + 1, last, cache);
                cache.put(key, fetched);
            }
            total += fetched;
        }
        return total;
    }
4

1 回答 1

0

递归算法

  • n正整数；
  • max最大总和大小；
  • return整数分区中每个被加数不超过最大值的部分。

这个变体没有无用的递归调用。

// start program
public static void main(String[] args) {
    int n = 5, max = 3;
    List<int[]> part = partition(n, max);
    // output
    for (int[] comb : part) System.out.println(Arrays.toString(comb));
}

/**
 * @param n   the positive integer
 * @param max the maximum summand size
 * @return the part of the integer partition,
 * where each summand does not exceed the maximum value
 */
public static List<int[]> partition(int n, int max) {
    List<int[]> list = new ArrayList<>();
    partition(n, max, "", list, new int[0]);
    return list;
}

public static void partition(
        int i, int max, String indent, List<int[]> master, int[] holder) {

    if (i == 0) {
        master.add(holder);
        System.out.println(indent + "i=" + i + ",max=" + max
                + "    comb=" + Arrays.toString(holder));
    }

    for (int j = Math.min(max, i); j >= 1; j--) {
        int[] temp = Arrays.copyOf(holder, holder.length + 1);
        temp[holder.length] = j;
        System.out.println(indent + "i=" + i + ",j=" + j + ",max=" + max
                + "  temp=" + Arrays.toString(temp));
        partition(i - j, j, indent + "  ", master, temp);
    }
}

递归树的输出n=5, max=3:

i=5,j=3,max=3  temp=[3]
  i=2,j=2,max=3  temp=[3, 2]
    i=0,max=2    comb=[3, 2]
  i=2,j=1,max=3  temp=[3, 1]
    i=1,j=1,max=1  temp=[3, 1, 1]
      i=0,max=1    comb=[3, 1, 1]
i=5,j=2,max=3  temp=[2]
  i=3,j=2,max=2  temp=[2, 2]
    i=1,j=1,max=2  temp=[2, 2, 1]
      i=0,max=1    comb=[2, 2, 1]
  i=3,j=1,max=2  temp=[2, 1]
    i=2,j=1,max=1  temp=[2, 1, 1]
      i=1,j=1,max=1  temp=[2, 1, 1, 1]
        i=0,max=1    comb=[2, 1, 1, 1]
i=5,j=1,max=3  temp=[1]
  i=4,j=1,max=1  temp=[1, 1]
    i=3,j=1,max=1  temp=[1, 1, 1]
      i=2,j=1,max=1  temp=[1, 1, 1, 1]
        i=1,j=1,max=1  temp=[1, 1, 1, 1, 1]
          i=0,max=1    comb=[1, 1, 1, 1, 1]

列表的输出n=5，max=3：

[3, 2]
[3, 1, 1]
[2, 2, 1]
[2, 1, 1, 1]
[1, 1, 1, 1, 1]

另请参阅：Java 中的整数分区

于 2021-05-05T11:59:44.880 回答