有一个由 n 个圆环组成的密码锁，和一个 n 位的密码 S（S 由 1~9 中的数字（包含 1 和 9）组成）。每次操作只能选择一个或位置连续的多个圆环拨动。当 S 中的字符从左到右依次显示在密码显示区时，密码锁会被打开。 已知每个圆环在密码显示区初始数字都为 0，请计算最少需要操作多少次，才能打开密码锁。 注意: 1、如果选择了其中一个圆环，可将该圆环中任意一个数字拨动到密码显示区，表示 1 次操作； 例如：将第 3 个圆环拨动到数字 4，表示 1 次操作： image 2、如果选择了位置连续的多个圆环，只能将这些圆环拨动成同一个数字，显示在密码显示区，表示 1 次操作。 例如：将连续的第 2 个到第 3 个圆环都拨动到数字 5，表示 1 次操作： image 例如： n = 5，S = "12321"；分别表示 5 个圆环组成的密码锁和密码 12321；将 5 位密码 1、2、3、2、1 从左到右依次显示在密码显示区，以下是操作次数最少的方案： 第一次操作，将 5 个初始状态为 0 的圆环全部拨动到数字 1： image 第二次操作，将第 2 个到第 4 个圆

```python # 读取输入 n = int(input()) S = input() # 创建 dp 数组，dp[i][j] 表示将从第 i 个到第 j 个圆环拨到目标状态的最少操作次数 dp = [[float('inf')] * n for _ in range(n)] # 初始化 dp 数组，单个圆环的情况，最少操作次数为 1 for i in range(n): dp[i][i] = 1 # 枚举区间长度 for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 # 先考虑最坏情况，即每次只操作一个圆环 for k in range(i, j): dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]) # 如果 S[i] 和 S[j] 相等，可以将它们一起操作 if S[i] == S[j]: dp[i][j] = min(dp[i][j], dp[i][j - 1], dp[i + 1][j]) # 输出结果 print(dp[0][n - 1]) ``` [2026-02-06 19:45:27 | AI问答 | 279点数解答]