动态规划解决字符串修改问题

这是一个字符串修改问题，可以使用动态规划来解决。

设 $dp[i][j]$ 表示将前 $i$ 个字符修改为前 $j$ 个字符为大写字母，后面都为小写字母的最少修改次数。

则对于第 $i$ 个字符，有两种情况：

1. 将第 $i$ 个字符改为大写字母，则需要将前 $i-1$ 个字符修改为前 $j-1$ 个字符为大写字母，后面都为小写字母的最少修改次数，加上将第 $i$ 个字符改为大写字母的一次修改。

2. 将第 $i$ 个字符改为小写字母，则需要将前 $i-1$ 个字符修改为前 $j$ 个字符为大写字母，后面都为小写字母的最少修改次数，加上将第 $i$ 个字符改为小写字母的一次修改。

则状态转移方程为：

$$
dp[i][j]=\begin{cases}
dp[i-1][j-1]+(s_i\text{为小写字母}), & j>0\\
dp[i-1][j]+(s_i\text{为大写字母}), & i>j
\end{cases}
$$

其中，$s_i$ 表示第 $i$ 个字符。

最终答案为 $\min\limits_{j=0}^{n}dp[n][j]$，其中 $n$ 为字符串长度。

时间复杂度为 $O(n^2)$。

以下是Python代码实现：

def modify_string(s):
    n = len(s)
    dp = [[float('inf')] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    for i in range(1, n + 1):
        for j in range(i + 1):
            if j > 0:
                dp[i][j] = dp[i - 1][j - 1] + (1 if s[i - 1].islower() else 0)
            if i > j:
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + (1 if s[i - 1].isupper() else 0))
    return min(dp[n])

# 测试
s = "AbCdE"
print(modify_string(s))  # 输出 2，将第 2 个字符和第 4 个字符改为小写字母即可