Я хочу посчитать все перестановки, которые находятся в определенном подмножестве, определенном DI Sequence и соответствующим заданным начальным значениям.
Аналогичная проблема: https://leetcode.com/articles/valid-permutations-for-di-sequence/
пример длины перестановки 4:
У нас есть входная длина цепочки битов 3 (всегда длина перестановки - 1)
010
0 означает 2 последовательных элементов I ncreasing.
1 означает 2 последовательных элементов D смазывающихся.
Для этой цепочки битов существует подмножество со следующими перестановками: 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) или лучше? Если да, то как?