DI序列定义的从x开始的排列计数的代码优化

Question

我想要计算DI Sequence定义的某个子集中的所有排列，并匹配给定的起始值。

类似的问题：https://leetcode.com/articles/valid-permutations-for-di-sequence/

排列长度为4的示例：

我们的输入位串长度为3(始终为置换长度- 1)

010

0表示2个连续元素是I递增的。

1表示2连续的元素是Decreasing。

对于此位串，存在具有以下排列的子集：1324,1423,2314,2413,3412

现在，我想计算所有排列的起始值为1,2

因此，我有这个方法调用：numsInDISequence(bitset, new int[]{1,1,0,0},4)

方法：

public int numsInDISequence(BitSet bits,  int[] start, int len){
    int[] dp =  Arrays.copyOf(start,start.length);
    int[] dp2 = new int[len-1];

    for(int i=0;i<len-1;i++){
        if(!bits.get(i)){
            for(int j=0; j<dp.length;j++){
                for(int k=j;k<dp2.length;k++) {
                   dp2[k]+=dp[j];
                }
             }
        }else{
             for(int j=0;j<dp.length;j++){
                for(int k=0;k<j;k++){
                    dp2[k]+=dp[j];
                 }
             }
         }
         dp = Arrays.copyOf(dp2,dp2.length);
         dp2 = new int[dp.length-1];
     }
     return dp[0];
}

这个算法在O(len^3)上运行，有没有可能将复杂度提高到O(len^2)或更好？如果是，是如何实现的？

Answer 1

我找到了一个解决方案，让它在O(len^2)复杂性内实现。只需从链接的类似问题中获取O(N^2)解决方案，并使用start数组作为初始dp数组。

similar problem