Python严格递增字符串（python递增输出字符）

liuian 2025-03-26 13:58 74 浏览

def min_modifications(s):
    n = len(s)
    dp_a = [0] * (n + 1)
    dp_b = [0] * (n + 1)
    
    for i in range(1, n + 1):
        if s[i-1] == 'A':
            dp_a[i] = dp_a[i-1]
            dp_b[i] = min(dp_a[i-1], dp_b[i-1]) + 1
        else:
            dp_b[i] = min(dp_a[i-1], dp_b[i-1])
            dp_a[i] = dp_a[i-1] + 1
    
    return min(dp_a[n], dp_b[n])

# 允许用户自定义输入
custom_input = input("请输入一个只包含 'A' 和 'B' 的字符串: ").strip().upper()
print("最小修改次数:", min_modifications(custom_input))

要解决这个问题，我们需要找到将给定字符串转换为严格递增字符串所需的最小修改次数。严格递增字符串的定义是从前往后字符的字典序是递增的，即字符只能是 'A' 或 'B'，并且不能有 'B' 出现在 'A' 的前面。

我们可以使用动态规划来解决这个问题。定义两个状态：

dp_a[i]：表示将字符串的前 i 个字符转换为严格递增字符串，并且第 i 个字符是 'A' 所需的最小修改次数。
dp_b[i]：表示将字符串的前 i 个字符转换为严格递增字符串，并且第 i 个字符是 'B' 所需的最小修改次数。

初始化时，dp_a[0] 和 dp_b[0] 都为 0，因为空字符串不需要任何修改。

对于每个字符 s[i]，我们更新 dp_a[i] 和 dp_b[i]：

如果 s[i] 是 'A'，则 dp_a[i] 可以是 dp_a[i-1]（前一个字符也是 'A'），而 dp_b[i] 可以是 min(dp_a[i-1], dp_b[i-1]) + 1（将 'A' 改为 'B'）。
如果 s[i] 是 'B'，则 dp_b[i] 可以是 min(dp_a[i-1], dp_b[i-1])（前一个字符可以是 'A' 或 'B'），而 dp_a[i] 可以是 dp_a[i-1] + 1（将 'B' 改为 'A'）。

最终，我们取 dp_a[n] 和 dp_b[n] 中的较小值作为结果，其中 n 是字符串的长度。

python 字典长度