动态规划求解符合约束的条码最小像素修改数问题求教

问题描述 #

输入参数：行数r、列数c、段最小宽度minWidth、段最大宽度maxWidth，以及一个r*c的0-1矩阵。
要求将矩阵转换为符合规则的条码：

• 条码由连续同色列构成的段组成，段宽度w_i需满足minWidth ≤ w_i ≤ maxWidth
• 相邻段颜色必须交替（不能连续出现同色段）
• 条码可从0或1色开始/结束
  任务：计算转换所需的最小像素修改次数（0与1互转）

示例输入与输出 #

示例输入 #

6 6 2 3
0 1 1 0 0 0
0 1 0 1 0 0
0 1 0 1 1 0
1 1 0 0 1 0
0 1 0 1 0 0
0 1 0 0 1 1

最优方案与输出 #

第1、2列设为1 - 5次修改
第3、4列设为0 - 4次修改
第5、6列设为1 - 8次修改
总和为17。

我的尝试与待完善点 #

我设计了三维DP数组dp[列索引][颜色(0/1)][当前段宽度]，表示处理到第列索引列时，当前段颜色为颜色、宽度为当前段宽度的最小修改次数，初始思路的代码框架如下（存在变量混淆与逻辑错误）：

# 初始化
dp[0][1][0] = 0
dp[0][0][0] = 0

for c in 1..s:
  for w in 1..maxWidth:
    if w > minWidth:
      dp[c][0][1] = min(dp[c][0][1], dp[c-1][1][w-1] + toWhite[i-1])
      dp[c][1][1] = min(dp[c][1][1], dp[c-1][0][w-1] + s - toWhite[i-1])

    dp[c][0][w] = min(dp[c][0][w], dp[c-1][0][w-1] + toWhite[i-1])
    dp[c][1][w] = min(dp[c][0][w], dp[c-1][1][w-1] + s - toWhite[i-1])

预期最终解为min(dp[c][0/1][w] for w ≥ minWidth)中的最小值，但当前思路存在多处错误，需要完善：

需修正的核心问题 #

1. 初始化逻辑
   原初始化的dp[0][0][0]和dp[0][1][0]应定义为虚拟起始状态（未处理任何列），此时段宽度为0，修改次数为0，作为所有合法段的起点。

2. 状态转移逻辑

   • 开启新段（w=1）：必须从上一个不同颜色的合法段（宽度≥minWidth）转移，而非原代码中错误的w-1=0状态。需取上一列该颜色所有合法宽度的最小dp值，再加上当前列转目标颜色的修改次数。
   • 延续当前段（2≤w≤maxWidth）：只能从上一个同颜色、段宽度为w-1的状态转移，且w不能超过maxWidth。

3. 变量定义与预处理

   • 预计算每列的修改成本：toWhite[j]表示第j列转为白色（0）的修改次数（统计该列中1的数量），toBlack[j] = r - toWhite[j]表示转为黑色（1）的修改次数。
   • 原代码中s、i等变量需替换为明确的c（总列数）、j（当前列索引）。

4. 效率优化
   每次计算新段转移时，若直接遍历所有合法宽度取最小值会增加时间复杂度，可维护两个辅助变量min_dp0和min_dp1，实时记录上一列颜色0、1的所有合法宽度（≥minWidth）的最小dp值，避免重复遍历。

修正后的DP框架示例 #

# 预处理每列的修改成本
toWhite = [sum(1 for row in matrix if row[j] == 1) for j in range(c)]
toBlack = [r - x for x in toWhite]

# 初始化DP数组：dp[j][color][w]，j从0到c，color 0/1，w从0到maxWidth
INF = float('inf')
dp = [[[INF]*(maxWidth+1) for _ in range(2)] for __ in range(c+1)]
dp[0][0][0] = 0
dp[0][1][0] = 0

# 维护上一列的合法段最小dp值
min_prev_0 = INF  # 上一列颜色0，宽度≥minWidth的最小dp值
min_prev_1 = INF

for j in range(1, c+1):
    # 先计算当前列延续段的状态
    for w in range(2, maxWidth+1):
        # 延续白色段
        if dp[j-1][0][w-1] != INF:
            dp[j][0][w] = dp[j-1][0][w-1] + toWhite[j-1]
        # 延续黑色段
        if dp[j-1][1][w-1] != INF:
            dp[j][1][w] = dp[j-1][1][w-1] + toBlack[j-1]
    
    # 计算开启新段的状态（w=1）
    # 从黑色合法段转白色新段
    if min_prev_1 != INF:
        dp[j][0][1] = min_prev_1 + toWhite[j-1]
    # 从白色合法段转黑色新段
    if min_prev_0 != INF:
        dp[j][1][1] = min_prev_0 + toBlack[j-1]
    
    # 更新当前列的合法段最小dp值，供下一列使用
    curr_min_0 = INF
    for w in range(minWidth, maxWidth+1):
        curr_min_0 = min(curr_min_0, dp[j][0][w])
    curr_min_1 = INF
    for w in range(minWidth, maxWidth+1):
        curr_min_1 = min(curr_min_1, dp[j][1][w])
    min_prev_0, min_prev_1 = curr_min_0, curr_min_1

# 最终答案：取最后一列所有合法段的最小dp值
final_min = INF
for color in [0,1]:
    for w in range(minWidth, maxWidth+1):
        final_min = min(final_min, dp[c][color][w])
print(final_min)

内容的提问来源于stack exchange，提问作者ajWee