我知道数字n的合成数为2^(n-1)，但这是我要解决的一个相似且更普遍的问题。

我有一组订购的商品：{i1,i2,i3,i4}

我搜索最佳构图，以使其最小化应用于每个部分的函数f的结果之和。 例如：序列{{i1},{i2},{i3,i4}}的值为f({i1}) + f({i2}) + f({i3,i4})。函数f不是线性的。

使用分而治之，我得出了O(2^n)的时间复杂度，因为它考虑了所有可能的构图，并且其中有2^n。

由于子问题是依赖的，因此我可以使用动态编程来优化算法。

例如：考虑S该函数计算最佳解。 S({i1,i4})将同时考虑S({i1}) + S({i2}) + S({i3,i4})和S({i1,i2}) + S({i3,i4})。每个考虑的解决方案的最后一项都相同，因此可以存储和重用，从而提高了时间复杂度。

但是最终的时间复杂度是多少？