2024 STEMA T6：解密T1188超难密码锁，Python区间DP解法揭秘！

以下是使用 Python 实现的代码： ```python # 读取输入 n = int(input()) S = input() # 创建一个三维的动态规划数组 dp # dp[i][j][k] 表示将区间 [i, j] 的圆环拨到数字 k 所需的最少操作次数 dp = [[[float('inf')] * 10 for _ in range(n)] for _ in range(n)] # 初始化 dp 数组 for i in range(n): for k in range(10): # 单个圆环拨到数字 k 的操作次数 dp[i][i][k] = abs(int(S[i]) - k) # 区间长度从 2 到 n 进行遍历 for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 for k in range(10): # 先考虑将整个区间 [i, j] 拨到数字 k 的情况 dp[i][j][k] = min(dp[i][j - 1][k], dp[i + 1][j][k]) + abs(int(S[j]) - k) # 枚举分割点，将区间 [i, j] 分成 [i, m] 和 [m + 1, j] for m in range(i, j): dp[i][j][k] = min(dp[i][j][k], dp[i][m][k] + dp[m + 1][j][k]) # 找到将整个区间 [0, n - 1] 拨到任意数字所需的最少操作次数 ans = float('inf') for k in range(10): ans = min(ans, dp[0][n - 1][k]) # 输出结果 print(ans) ``` 代码解释： 1. 输入读取：首先读取圆环的数量 `n` 和密码字符串 `S`。 2. 动态规划数组初始化：创建一个三维数组 `dp`，其中 `dp[i][j][k]` 表示将区间 `[i, j]` 的圆环拨到数字 `k` 所需的最少操作次数。对于单个圆环，将其拨到数字 `k` 的操作次数为该圆环的目标数字与 `k` 的差值的绝对值。 3. 区间动态规划：通过枚举区间长度、区间起始位置和目标数字，计算将区间 `[i, j]` 拨到数字 `k` 的最少操作次数。枚举分割点，将区间 `[i, j]` 分成两个子区间，取最小操作次数。 4. 结果计算：在所有可能的目标数字中，找到将整个区间 `[0, n - 1]` 拨到该数字所需的最少操作次数。 5. 输出结果：输出最少操作次数。 复杂度分析： - 时间复杂度：$O(n^3 \times 10)$，其中 $n$ 是圆环的数量。 - 空间复杂度：$O(n^2 \times 10)$，主要用于存储动态规划数组。 ######[AI问答 | 718点数解答 | 2025-11-08 22:09:01]