title
给你一个下标从 0 开始的二进制字符串 s ，表示一个列车车厢序列。s[i] = '0' 表示第 i 节车厢 不 含违禁货物，而 s[i] = '1' 表示第 i 节车厢含违禁货物。
作为列车长，你需要清理掉所有载有违禁货物的车厢。你可以不限次数执行下述三种操作中的任意一个：
- 从列车 左 端移除一节车厢（即移除
s[0]），用去 1 单位时间。 - 从列车 右 端移除一节车厢（即移除
s[s.length - 1]），用去 1 单位时间。 - 从列车车厢序列的 任意位置 移除一节车厢，用去 2 单位时间。
返回移除所有载有违禁货物车厢所需要的 最少 单位时间数。
注意，空的列车车厢序列视为没有车厢含违禁货物。
示例 1：
输入：s = "1100101"
输出：5
解释：
一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
- 从右端移除一节车厢 1 次。所用时间是 1 。
- 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。
总时间是 2 + 1 + 2 = 5 。
一种替代方法是：
- 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
- 从右端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。
总时间也是 2 + 3 = 5 。
5 是移除所有载有违禁货物的车厢所需要的最少单位时间数。
没有其他方法能够用更少的时间移除这些车厢。
示例 2：
输入：s = "0010"
输出：2
解释：
一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从左端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。
总时间是 3.
另一种从序列中移除所有载有违禁货物的车厢的方法是：
- 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。
总时间是 2.
另一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从右端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
总时间是 2.
2 是移除所有载有违禁货物的车厢所需要的最少单位时间数。
没有其他方法能够用更少的时间移除这些车厢。
提示：
1 <= s.length <= 2 * 105s[i]为'0'或'1'
solution
前后缀分解+ dp
考虑将列车分成左右两部分，枚举分割线，分别计算这两部分的最少时间。
class Solution:
def minimumTime(self, s: str) -> int:
n = len(s)
l = [n] * (n + 1)
r = [n] * (n + 1)
for i in range(n):
if s[i] == "0":
l[i] = l[i - 1] if i > 0 else 0
else:
l[i] = min(i + 1, (l[i - 1] + 2) if i > 0 else 1)
for i in range(n - 1, -1, -1):
if s[i] == "0":
r[i] = r[i + 1] if i < n - 1 else 0
else:
r[i] = min(n - i, (r[i + 1] + 2) if i < n - 1 else 1)
ans = min(n, l[n - 1], r[0])
for i in range(n - 1):
ans = min(ans, l[i] + r[i + 1])
return ans