java - 解决 "Partition Function Q"或总和为 n 的序列总数的有效方法

Question

问题是这样的:你可以用至少 2 个数字组成多少个序列，其中序列中的所有数字总和为 n。

http://mathworld.wolfram.com/PartitionFunctionQ.html

使用方程here * 我能够得到以下功能:

public static int GetSequences(int n, int k) {
    if(n <= k) return 0;
    int result = 1;
    for(int i = k + 1; i < n; i++) {
        result += GetSequences(n - i, i);
    }
    return result;
}

但是求解时间与n呈指数关系。在 n = 180 左右时，可能需要 10 秒以上才能完成。

我尝试使用 HashMap 来存储以前解决的值，但我得到了非常疯狂的结果。

static Map<Long,Long> cache = new HashMap<Long,Long>();

public static int solve(int n) {
    for(int i = 3; i <= n; i++) {
        cache.put((long)i, (long)GetSequences(i, 0));
    }
    return cache.get((long) n).intValue() - 1;
}

public static int GetSequences(int n, int k) {
    if(n <= k) return 0;
    if(cache.containsKey((long)k)) {
        return cache.get((long)k).intValue();
    }
    int result = 1;
    for(int i = k + 1; i < n; i++) {
        result += GetSequences(n - i, i);
    }
    return result;
}

如何提高效率以便更快地生成序列总数？

*:为了让GetSequences(n,k)函数解决链接中的问题，结果必须减去1以考虑序列[n,0 ]

Answer 1

您可以使用内存来解决它。在这种方法中，每当您解决子问题时，您都会存储结果，以便每当子问题重复时，您只需进行查找而不是计算。

下面的程序应该会给你一些想法。它不是一个非常有效的解决方案，但它确实大大减少了运行时间。

public class Partition {
    public static void main(String[] args) {
        System.out.println(GetSequences(180, 1, new HashMap<>()));
    }

    public static int GetSequences(int n, int k, Map<Pair, Integer> data) {
        if (n <= k)
            return 0;

        int result = 1;

        for (int i = k + 1; i < n; i++) {
            Pair p = new Pair(n - i, i);
            if (data.containsKey(p)) {
                result += data.get(p);
            } else {
                int res = GetSequences(n - i, i, data);
                data.put(p, res);
                result += res;
            }
        }
        return result;
    }

    static class Pair {
        int n;
        int k;

        Pair(int n, int k) {
            this.n = n;
            this.k = k;
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + k;
            result = prime * result + n;
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Pair other = (Pair) obj;
            if (k != other.k)
                return false;
            if (n != other.n)
                return false;
            return true;
        }

    }

}