跳转至

状态压缩动态规划⚓︎

状态压缩动态规划（\text{State Compression DP}）是一种用于解决涉及多个状态组合的问题的动态规划技术。其核心思想是通过使用位掩码（\text{bitmask}）来表示状态，从而有效地减少状态空间的大小。

二元状态⚓︎

在许多问题中，状态可以用二进制位来表示。例如，在一个有 n 个元素的集合中，每个元素可以处于两种状态之一（选中或未选中）。可以使用一个长度为 n 的二进制数来表示这些状态，其中第 i 位为 1 表示第 i 个元素被选中，为 0 表示未选中。

常见问题类型

  • 集合划分、子集 \text{DP}
  • 旅行商问题（\text{TSP}）
  • 排列计数
  • \text{Hamilton} 路径
  • 匹配、覆盖、分配类问题

dp[mask][i] 表示当前访问的集合为 mask，并且最后停在节点 i 的最小代价。则状态转移方程为：

dp[mask \mid (1 \ll j)][j] = \min \big( dp[mask \mid (1 \ll j)][j],\ dp[mask][i] + cost[i][j] \big)

其中：

  • mask 表示访问过的节点集合（二进制掩码）
  • i, j 为节点编号，且 j \notin mask

时间复杂度：O(n^2 \cdot 2^n)，适用于 n \leq 20 的情况。

划分为k个相等的子集

给定一个整数数组 nums 和一个整数 k，判断是否可以将该数组分成 k 个非空子集，其总和都相等。

C++
#include <functional>
#include <numeric>
#include <vector>
using namespace std;

class Solution {
 public:
  bool canPartitionKSubsets(vector<int> &nums, int k) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % k != 0) { return false; }  // 总和不能被k整除
    int target = sum / k;
    int n      = nums.size();

    // 状态压缩dp, dp[status]表示状态status是否可行
    vector<int> dp(1 << n, -1);
    // status: 当前选择的数字集合, target: 每个子集的目标和, sum: 当前子集的和,
    // rest_k: 剩余子集数量
    function<bool(int, int, int)> dfs = [&](int status, int sum, int rest_k) {
      // 所有数字都被选择完, 且正好划分为k个子集
      if (rest_k == 0) { return status == 0; }
      if (dp[status] != -1) { return dp[status] == 1; }  // 记忆化
      bool ok = false;                                   // 当前状态是否可行
      // 尝试选择一个数字加入当前子集
      for (int i = 0; i < n; ++i) {
        // 数字i已经被选择
        if ((status & (1 << i)) == 0) { continue; }
        // 如果加入数字i后超过目标和, 则跳过
        if (sum + nums[i] > target) { continue; }
        int next_status = status ^ (1 << i);
        if (sum + nums[i] == target) {  // 当前子集已满, 开始下一个子集
          ok = dfs(next_status, 0, rest_k - 1);
        } else {  // 继续填充当前子集
          ok = dfs(next_status, sum + nums[i], rest_k);
        }
        if (ok) { break; }  // 找到一个可行解即可
      }
      dp[status] = ok ? 1 : 0;
      return ok;
    };
    return dfs((1 << n) - 1, 0, k);
  }
};
C++
#include <numeric>
#include <vector>
using namespace std;

class Solution {
 public:
  bool canPartitionKSubsets(vector<int> &nums, int k) {
    int n   = nums.size();
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % k != 0) return false;
    int target = sum / k;
    vector<int> dp(1 << n, -1);
    dp[0] = 0;  // 初始状态，未选择任何元素时，当前子集和为 0

    for (int mask = 0; mask < (1 << n); ++mask) {
      if (dp[mask] == -1) { continue; }  // 跳过不可达状态
      for (int i = 0; i < n; ++i) {
        if ((mask & (1 << i)) != 0) { continue; }  // 元素已被选择
        int next_sum = dp[mask] + nums[i];
        if (next_sum <= target) {
          dp[mask | (1 << i)] = next_sum % target;  // 更新状态
        }
      }
    }
    return dp[(1 << n) - 1] == 0;  // 检查是否所有元素都被选择且子集和为目标值
  }
};

轮廓线 DP⚓︎

轮廓线 \text{DP}（\text{Profile DP}）是一种用于解决二维网格问题的动态规划技术。其核心思想是逐行或逐列扫描棋盘，用轮廓线描述当前行（或列）的状态（通过使用位掩码来表示当前行的状态）。

常见问题类型

  • 棋盘覆盖问题（多米诺骨牌填充）
  • 障碍填充问题
  • 带限制的格点计数（如放置棋子、路径计数等）
  • 图形填充问题

dp[i][state]表示处理到第 i 行（或列），当前轮廓线状态为 state 的方案数。则状态转移方程为：

dp[i+1][state'] = \sum_{\text{legal transitions}} dp[i][state]

其中：

  • state 通常用二进制或三进制表示当前行的格子占用状态
  • 通过枚举所有合法放置方式更新下一行的 state'
互不侵犯

在 N * N 的棋盘上放置K个国王, 使得任意两个国王不在相邻的格子上(八个方向)的方案。

C++
#include <cstdint>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int N, K;
  cin >> N >> K;

  auto dp      = vector(N, vector(N, vector(1 << N, vector(2, vector<int64_t>(K + 1, -1)))));
  auto get_bit = [](int state, int j) { return (state >> j) & 1; };
  auto set_bit = [](int state, int j, int value) {
    return value == 0 ? (state & ~(1 << j)) : (state | (1 << j));
  };
  // i: 当前行, j: 当前列, state: 当前行状态, left_up: 左上角是否放置, rest_k:
  // 剩余国王数量
  std::function<int64_t(int, int, int, int, int)> dfs
      = [&](int i, int j, int state, int left_up, int rest_k) -> int64_t {
    // 所有行处理完, 且正好放置k个国王
    if (i == N) { return rest_k == 0; }
    if (j == N) { return dfs(i + 1, 0, state, 0, rest_k); }  // 换行
    if (dp[i][j][state][left_up][rest_k] != -1) { return dp[i][j][state][left_up][rest_k]; }
    // 获取当前位置的左边, 上边, 右上角的状态, 左上角状态由参数获得
    int left     = (j == 0) ? 0 : get_bit(state, j - 1);
    int up       = get_bit(state, j);
    int right_up = (j == N - 1) ? 0 : get_bit(state, j + 1);
    int64_t res  = 0;
    // 从下一列继续, 设置当前位置为0, 下一个位置的左上角状态为当前位置的上方状态
    // 不放置国王
    res += dfs(i, j + 1, set_bit(state, j, 0), up, rest_k);
    // 放置国王, 当前位置的左边, 左上角, 上边, 右上角都不能有国王,
    // 且剩余国王数量要大于0
    if (rest_k > 0 && left == 0 && left_up == 0 && up == 0 && right_up == 0) {
      res += dfs(i, j + 1, set_bit(state, j, 1), up, rest_k - 1);
    }
    dp[i][j][state][left_up][rest_k] = res;  // 记忆化
    return res;
  };
  cout << dfs(0, 0, 0, 0, K) << "\n";
  return 0;
}
C++
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int N, K;
  cin >> N >> K;

  auto get_bit = [](int state, int j) { return (state >> j) & 1; };
  auto set_bit = [](int state, int j, int value) {
    return value == 0 ? (state & ~(1 << j)) : (state | (1 << j));
  };
  auto dp = vector(N + 1, vector(1 << N, vector(2, vector<int64_t>(K + 1))));
  for (int s = 0; s < (1 << N); ++s) {
    for (int k = 0; k <= K; k++) { dp[0][s][0][k] = k == 0 ? 1 : 0; }
  }
  for (int i = N - 1; i >= 0; --i) {
    // j == N
    for (int s = 0; s < (1 << N); ++s) {
      for (int k = 0; k <= K; k++) { dp[N][s][0][k] = dp[N][s][1][k] = dp[0][s][0][k]; }
    }
    // j < N
    for (int j = N - 1; j >= 0; --j) {
      for (int s = 0; s < (1 << N); ++s) {
        for (int left_up = 0; left_up <= 1; ++left_up) {
          for (int k = 0; k <= K; k++) {
            // 获取当前位置的左边, 上边, 右上角的状态, 左上角状态由参数获得
            int left     = (j == 0) ? 0 : get_bit(s, j - 1);
            int up       = get_bit(s, j);
            int right_up = (j == N - 1) ? 0 : get_bit(s, j + 1);
            int64_t res  = 0;
            // 从下一列继续, 设置当前位置为0,
            // 下一个位置的左上角状态为当前位置的上方状态 不放置国王
            res += dp[j + 1][set_bit(s, j, 0)][up][k];
            // 放置国王, 当前位置的左边, 左上角, 上边, 右上角都不能有国王,
            // 且剩余国王数量要大于0
            if (k > 0 && left == 0 && left_up == 0 && up == 0 && right_up == 0) {
              res += dp[j + 1][set_bit(s, j, 1)][up][k - 1];
            }
            dp[j][s][left_up][k] = res;
          }
        }
      }
    }
  }
  cout << dp[0][0][0][K] << "\n";
  return 0;
}

三进制状态压缩⚓︎

三进制状态压缩（\text{Ternary State Compression}）是一种用于解决涉及三种状态组合（例如：未选、选 A、选 B）的问题的动态规划技术。其核心思想是通过使用三进制数来表示状态，从而有效地减少状态空间的大小。

状态多于二元的情况, 可以用更高进制的数表示。三进制状态表示如下：

m 列的状态可用一个整数 s 表示，s 的三进制展开的每一位代表一列的状态（0、1、2）

状态 s = s[0] * 3^0 + s[1] * 3^1 + \dots + s[m-1] * 3^{(m-1)}

  • get(s, j)：取 s 的三进制展开的第 j 位（第 j 列的状态），即：(s // 3^j) \% 3
  • set(s, j, v)：把 s 的三进制展开的第 j 位设为 v，返回新状态，即 s + (v - get(s, j)) * 3^j

常见问题类型

  • 轮廓线 DP 优化版（当每个格点三种状态时）
  • 涂色问题（三种颜色）
  • 匹配 / 放置带方向限制的问题

预处理

  • 预处理所有可能的状态和状态转移，减少运行时计算
  • 使用位运算优化状态表示和转换
用三种不同颜色为网格涂色

给你两个整数 m 和 n，表示一个 m 行 n 列的网格。请你给这个网格的每个格子涂色，且满足以下条件：

  • 每个格子只能涂成 1、2 或 3 三种颜色之一。
  • 相邻格子（上下或者左右）颜色不能相同。

返回你给网格涂色的方案数。由于答案可能很大，请你返回方案数对 10^9 + 7 取余的结果。

C++
#include <cstdint>
#include <functional>
#include <utility>
#include <vector>
using namespace std;

class Solution {
 public:
  int colorTheGrid(int m, int n) {
    const int mod  = 1e9 + 7;

    auto get_state = [](int64_t s, int64_t pow_j) { return (s / pow_j) % 3; };
    auto set_state = [](int64_t s, int64_t pow_j, int v) {
      int64_t old = (s / pow_j) % 3;
      return s + (v - old) * pow_j;
    };

    if (m > n) { swap(m, n); }  // 保证 m <= n
    int64_t max_state = pow(3, m);
    // 获取一行有效状态
    vector<int> initial_states;
    std::function<void(int, int, int)> dfs_init = [&](int j, int s, int pow_j) {
      if (j == m) {
        initial_states.push_back(s);
        return;
      }
      // 获取左边的状态, pow_j / 3 就是 3^(j-1)
      int left = (j == 0) ? -1 : get_state(s, pow_j / 3);
      for (int v = 0; v < 3; ++v) {
        if (v != left) { dfs_init(j + 1, set_state(s, pow_j, v), pow_j * 3); }
      }
    };
    dfs_init(0, 0, 1);
    // 分别对应行、列、状态空间
    auto dp = vector(n, vector(m, vector<int64_t>(pow(3, m), -1)));
    function<int64_t(int, int, int64_t, int64_t)> dfs
        = [&](int i, int j, int64_t s, int64_t pow_j) -> int64_t {
      // 所有行处理完
      if (i == n) { return 1; }
      if (j == m) { return dfs(i + 1, 0, s, 1); }  // 换行
      if (dp[i][j][s] != -1) { return dp[i][j][s]; }
      int64_t res = 0;
      // 获取当前位置的左边和上边的状态
      int left = (j == 0) ? -1 : get_state(s, pow_j / 3);
      int up   = get_state(s, pow_j);
      for (int v = 0; v < 3; ++v) {
        if (v != left && v != up) {  // 与左边和上边不同色
          res = (res + dfs(i, j + 1, set_state(s, pow_j, v), pow_j * 3)) % mod;
        }
      }
      dp[i][j][s] = res;
      return res;
    };
    int64_t ans = 0;
    for (int s : initial_states) { ans = (ans + dfs(1, 0, s, 1)) % mod; }
    return ans;
  }
};

评论