title: “SOS DP”
date: 2024-11-03 06:29:02
updated: 2024-11-03 15:19:23
tag: [“notion”, “Algorithm”, “动态规划”]
categories: “Algorithm”
mathjax: true
comments: true
description: ‘

• SOS DP

SOS DP

高维度数组求前缀和

例如4维数组f[d1][d2][d3][d4]，每个维度分别为d1,d2,d3,d4

int f[d1][d2][d3][d4];
for (int i1=1; i1<d1; i1++) {
    for (int i2=1; i2<d2; i2++) {
        for (int i3=1; i3<d3; i3++) {
            for (int i4=1; i4<d4; i4++) {
                f[i1][i2][i3][i4] += f[i1][i2][i3][i4-1];
            }
        }
    }
}
for (int i1=1; i1<d1; i1++) {
    for (int i2=1; i2<d2; i2++) {
        for (int i3=1; i3<d3; i3++) {
            for (int i4=1; i4<d4; i4++) {
                f[i1][i2][i3][i4] += f[i1][i2][i3-1][i4];
            }
        }
    }
}
for (int i1=1; i1<d1; i1++) {
    for (int i2=1; i2<d2; i2++) {
        for (int i3=1; i3<d3; i3++) {
            for (int i4=1; i4<d4; i4++) {
                f[i1][i2][i3][i4] += f[i1][i2-1][i3][i4];
            }
        }
    }
}
for (int i1=1; i1<d1; i1++) {
    for (int i2=1; i2<d2; i2++) {
        for (int i3=1; i3<d3; i3++) {
            for (int i4=1; i4<d4; i4++) {
                f[i1][i2][i3][i4] += f[i1-1][i2][i3][i4];
            }
        }
    }
}

对于有$n$维的数组，第$i$维度为$d_i$，求前缀和其时间复杂度是$\prod \limits_{i=1}^n d_i$
若每个维度大小都相等，$d_i=c$，那么时间复杂度是$c^n$

若$c=2$，这些下标可以用一个$n$位二进制数来表示，二进制数可以代表集合，求前缀和可以认为是求子集和。

求子集和

使用维度大小为2的高维度数组表示子集

int f[2][2][2][2];
for (int i1=1; i1<2; i1++) {
    for (int i2=1; i2<2; i2++) {
        for (int i3=1; i3<2; i3++) {
            for (int i4=1; i4<2; i4++) {
                f[i1][i2][i3][i4] += f[i1][i2][i3][i4-1];
            }
        }
    }
}
for (int i1=1; i1<2; i1++) {
    for (int i2=1; i2<2; i2++) {
        for (int i3=1; i3<2; i3++) {
            for (int i4=1; i4<2; i4++) {
                f[i1][i2][i3][i4] += f[i1][i2][i3-1][i4];
            }
        }
    }
}
for (int i1=1; i1<2; i1++) {
    for (int i2=1; i2<2; i2++) {
        for (int i3=1; i3<2; i3++) {
            for (int i4=1; i4<2; i4++) {
                f[i1][i2][i3][i4] += f[i1][i2-1][i3][i4];
            }
        }
    }
}
for (int i1=1; i1<2; i1++) {
    for (int i2=1; i2<2; i2++) {
        for (int i3=1; i3<2; i3++) {
            for (int i4=1; i4<2; i4++) {
                f[i1][i2][i3][i4] += f[i1-1][i2][i3][i4];
            }
        }
    }
}

这样非常不elegent，可以利用二进制数的特性，四重for循环可改为枚举二进制数 可以枚举4个二进制位确定是哪个下标累加

for (int i=0; i<4; i++) {
    for (int j=0; j<1<<4; j++) {
        int i1=j>>3, i2=j>>2&1, i3=j>>1&1, i4=j&1;
        f[i1][i2][i3][i4] += f[i1-(i==0)][i2-(i==1)][i3-(i==2)][i4-(i==3)];
    }
}

维度大小都是2的高维度数组，用一维数组来表示其实更好处理，只需要将下标看作n位二进制数

对于n个元素的子集，求子集和，时间复杂度$O(n2^n)$

for (int i=0; i<n; i++) {
    for (int j=0; j<1<<n; j++) {
        if (j>>i&1) f[j] += f[j^(1<<i)];
    }
}

SOS DP

高维度前缀和也称为SOS DP (Sum over Subsets dynamic programming)

以dp视角看待求子集和，$dp_{i,j}$代表只处理了二进制集合$j$的低$i$位的子集和，$dp_{0,i}$对应初始化的$f_i$

状态转移

• $j$的第$i$位为1时, $dp_{i, j} = dp_{i-1, j} + dp_{i-1, j’}$，$j’$代表$j$移除了第i位的1。
• $j$的第$i$位为0时，$dp_{i, j} = dp_{i-1,j}$

时间复杂度是$O(n2^n)$

int dp[n+1][1<<n];
// dp[0][] = f[]
for (int i=1; i<=n; i++) {
    for (int j=0; j<1<<n; j++) {
        if (j>>(i-1)&1)
            dp[i][j] = dp[i-1][j] + dp[i-1][j^(1<<i-1)];
        else 
            dp[i][j] = dp[i-1][j];
    }
}

例如$n=5$时，

$dp_{3, 10101} = dp_{2, 10101}+dp_{2, 10001} \\= dp_{1, 10101} + dp_{1, 10001} \\= dp_{0, 10101} + dp_{0, 10100} + dp_{0, 10001} + dp_{0, 10000}$

二进制10101末3位的子集分别是10101,10100,10001,10000

由于$dp_{i,j} = dp_{i-1, j}+dp_{i, j’}$，而$j’<j$，使用滚动数组，从小到大枚举2进制状态进行覆盖是安全的。

for (int i=0; i<n; i++) {
    for (int j=0; j<1<<n; j++) {
        if (j>>i&1) f[j] += f[j^(1<<i)];
    }
}

枚举子集的子集

采用枚举子集的子集的方式计算子集和

时间复杂度是$O(3^n)$

小于$2^n$的非负整数中，含有$k$个$1$的二进制数个数有$\binom{n}{k}$个，其子集有$2^k$个

$\sum \limits_{k=0}^{n} \binom{n}{k}2^k = (1+2)^n$ 二项式展开

int f[1<<n], sf[1<<n];
for (int i=0; i<1<<n; i++) {
    for (int j=i; j!=0; j = (j-1)&i) { // 枚举i的子集，i的二进制1的个数为k，时间复杂度O(2^k)
        sf[i] += f[j];
    }
}