求替换字符串!后最小(x*count1+y*count2)值的正确解法

问题描述 #

给定长度为n的字符串s（仅含0、1、!）及整数x、y，需将!替换为0或1，统计子序列"01"的数量count1与子序列"10"的数量count2，计算sum=(xcount1)+(ycount2)的最小值，结果对10^9+7取模。

示例

1. 输入：s="101!1",x=2,y=3，结果为9
2. 输入：n=7,s="!!!!!!!",x=23,y=47，结果为0

约束

• n∈[1,10^{5]，x、y∈[0,10}5]

现有代码问题分析 #

你提供的代码只考虑了两种极端情况：将所有!替换为0，或全部替换为1。但实际上最优解往往需要部分!替换为0、部分替换为1——比如当x远小于y时，应尽量让0都出现在1前面，减少"10"子序列的数量；当y远小于x时，则相反。这种极端情况的枚举无法覆盖所有最优场景，导致长字符串用例失败。

正确解法：动态规划 #

通过动态规划维护两种状态的最优解：

• 状态0：处理到当前字符时，将其替换为0的最小sum，以及累计的0、1数量
• 状态1：处理到当前字符时，将其替换为1的最小sum，以及累计的0、1数量

每个字符处理时，根据字符类型（0/1/!），从之前的最优状态转移，确保每一步都选择当前最小的sum。

正确代码 #

import java.util.*;

public class Solution {
    private static final int MOD = 1000000007;
    private static final long INF = Long.MAX_VALUE / 2; // 避免加法溢出

    public static void main(String[] args) {
        System.out.println(solve("101!1", 2, 3)); // 输出9
        System.out.println(solve("!!!!!!!", 23, 47)); // 输出0
        System.out.println(solve("!0!1!", 1, 100)); // 输出6
    }

    static int solve(String s, int x, int y) {
        int n = s.length();
        // sum0: 当前字符换0的最小sum; z0: 累计0数; o0: 累计1数
        long sum0 = INF, z0 = 0, o0 = 0;
        // sum1: 当前字符换1的最小sum; z1: 累计0数; o1: 累计1数
        long sum1 = INF, z1 = 0, o1 = 0;

        // 初始化第一个字符
        char first = s.charAt(0);
        if (first == '0') {
            sum0 = 0;
            z0 = 1;
            o0 = 0;
        } else if (first == '1') {
            sum1 = 0;
            z1 = 0;
            o1 = 1;
        } else { // 处理'!'
            sum0 = 0;
            z0 = 1;
            o0 = 0;
            sum1 = 0;
            z1 = 0;
            o1 = 1;
        }

        for (int i = 1; i < n; i++) {
            char c = s.charAt(i);
            long newSum0 = INF, newZ0 = 0, newO0 = 0;
            long newSum1 = INF, newZ1 = 0, newO1 = 0;

            // 尝试将当前字符换为0
            if (c == '0' || c == '!') {
                if (sum0 <= sum1) {
                    newSum0 = sum0 + y * o0;
                    newZ0 = z0 + 1;
                    newO0 = o0;
                } else {
                    newSum0 = sum1 + y * o1;
                    newZ0 = z1 + 1;
                    newO0 = o1;
                }
            }

            // 尝试将当前字符换为1
            if (c == '1' || c == '!') {
                if (sum0 <= sum1) {
                    newSum1 = sum0 + x * z0;
                    newO1 = o0 + 1;
                    newZ1 = z0;
                } else {
                    newSum1 = sum1 + x * z1;
                    newO1 = o1 + 1;
                    newZ1 = z1;
                }
            }

            // 更新状态
            sum0 = newSum0;
            z0 = newZ0;
            o0 = newO0;
            sum1 = newSum1;
            z1 = newZ1;
            o1 = newO1;
        }

        long minSum = Math.min(sum0, sum1);
        return (int) (minSum % MOD);
    }
}

代码说明 #

• 用INF标记不可达状态（比如字符为0时无法替换为1）
• 每一步选择从之前的最小sum状态转移，确保当前状态的sum最优
• 使用long类型避免数值溢出，最后统一取模10^9+7

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