洛谷P2622 关灯问题II引发的关于DP实现形式及后效性的思考

  动态规划要求已经求解的子问题不受后续阶段的影响，即无后效性。而在这种递推的实现方式中，后面枚举的状态可能更新前面已经枚举过的状态。也就是说，这种递推的实现方式是具有后效性的。
以这组数据为例

3
3
1 -1 1 
0 1 -1 
0 0 1

  正解应为 \(3\) 次（\(111 \to 010 \to 100 \to 000\)） 。

  而在递推时，\(100\) 在 \(010\) 之前被已被枚举，在 \(010\) 更新了 \(100\) 之后无法再通过 \(100\) 来得到目标状态 \(000\)，便会得出 \(-1\)（无解）的错误答案。

//递推
#include <stdio.h>
#include <string.h>
#include <algorithm>
using std::min;

int m, n, a[110][10], f[1 << 10];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &a[i][j]);
        }
    }
    memset(f, 0x3f, sizeof(f));
    f[(1 << n) - 1] = 0;
    for (int i = (1 << n) - 1; i >= 0; --i) {
        for (int k = 1; k <= m; ++k) {
            int t = i;
            for (int j = 0; j < n; ++j) {
                if (a[k][j] == 1 && (i & (1 << j))) t ^= 1 << j;
                if (a[k][j] == -1 && !(i & (1 << j))) t ^= 1 << j;
            }
            f[t] = min(f[t], f[i] + 1);
        }
    }
    printf("%d", f[0] == 0x3f3f3f3f ? -1 : f[0]);
    return 0;
}

  对于该题，适合使用记忆化BFS的实现方式。用BFS来进行记忆化搜索的这种实现方式可能比较少见，其实只是对于状态的遍历顺序不同。由于BFS的特性，每个状态在第一次被扩展到时便得到最优解。

//记忆化BFS
#include <stdio.h>
#include <string.h>
#include <algorithm>
using std::min;

int m, n, head, tail, q[10000], a[110][10], f[1 << 10];
bool vis[1 << 10];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &a[i][j]);
        }
    }
    memset(f, 0x3f, sizeof(f));
    f[(1 << n) - 1] = 0;
    q[tail++] = (1 << n) - 1;
    vis[(1 << n) - 1] = true;
    while (head < tail) {
        int cur = q[head++];
        for (int i = 1; i <= m; ++i) {
            int t = cur;
            for (int j = 0; j < n; ++j) {
                if (a[i][j] == 1 && (cur & (1 << j))) t ^= 1 << j;
                if (a[i][j] == -1 && !(cur & (1 << j))) t ^= 1 << j;
            }
            if (vis[t]) continue;
            vis[t] = true;
            f[t] = f[cur] + 1;
            q[tail++] = t;
            if (t == 0) {
                printf("%d", f[t]);
                return 0;
            }
        }
    }
    printf("-1");
    return 0;
}

  当然，使用DFS+剪枝也可较为高效的解决该题。不过终究还是会重复遍历一些状态，比DP略慢。