小红拿到了一个01串。所谓01串,指仅由’0’和’1’两种字符组成的字符串。 小红可以进行任意次以下操作: 选择字符串的一个字符,将其取反(’0’变’1’或者’1’变’0’)。 小红定义一个01串为好串,当且仅当该01串不包含”010″子串和”101″子串。 例如,”1001″是好串,但”100100″则不是好串。 小红想知道,自己最少操作多少次可以将给定字符串变成好串?
区块链毕设网qklbishe.com为您提供问题的解答
小红拿到了一个01串。所谓01串,指仅由’0’和’1’两种字符组成的字符串。
小红可以进行任意次以下操作:
- 选择字符串的一个字符,将其取反(’0’变’1’或者’1’变’0’)。
小红定义一个01串为好串,当且仅当该01串不包含”010″子串和”101″子串。
例如,”1001″是好串,但”100100″则不是好串。
小红想知道,自己最少操作多少次可以将给定字符串变成好串?
n = len(s)
if n < 3:
print(0)
else:
# 初始化动态规划的前两个字符状态
prev_dp = {
(‘0’, ‘0’): (s[0] != ‘0’) + (s[1] != ‘0’),
(‘0’, ‘1’): (s[0] != ‘0’) + (s[1] != ‘1’),
(‘1’, ‘0’): (s[0] != ‘1’) + (s[1] != ‘0’),
(‘1’, ‘1’): (s[0] != ‘1’) + (s[1] != ‘1’),
}
# 允许的第三个字符的映射
allowed_c_map = {
(‘0’, ‘0’): [‘0’, ‘1’],
(‘0’, ‘1’): [‘1’],
(‘1’, ‘0’): [‘0’],
(‘1’, ‘1’): [‘0’, ‘1’],
}
for i in range(2, n):
current_dp = {}
current_char = s[i]
for (a, b), cost in prev_dp.items():
allowed_c = allowed_c_map.get((a, b), [])
for c in allowed_c:
delta = 1 if c != current_char else 0
new_state = (b, c)
new_cost = cost + delta
# 更新当前状态的最小成本
if new_state in current_dp:
if new_cost < current_dp[new_state]:
current_dp[new_state] = new_cost
else:
current_dp[new_state] = new_cost
prev_dp = current_dp
# 取所有可能状态的最小值
print(min(prev_dp.values()))
以上就是关于问题小红拿到了一个01串。所谓01串,指仅由’0’和’1’两种字符组成的字符串。
小红可以进行任意次以下操作:
选择字符串的一个字符,将其取反(’0’变’1’或者’1’变’0’)。 小红定义一个01串为好串,当且仅当该01串不包含”010″子串和”101″子串。
例如,”1001″是好串,但”100100″则不是好串。
小红想知道,自己最少操作多少次可以将给定字符串变成好串?的答案
欢迎关注区块链毕设网-
web3一级市场套利打新赚钱空投教程
区块链NFT链游项目方科学家脚本开发培训
从业7年-专注一级市场
微信:btc9767
TELEGRAM :https://t.me/btcok9
具体资料介绍
web3的一级市场千万收益的逻辑
进群点我
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台-javagopython毕设 » 小红拿到了一个01串。所谓01串,指仅由’0’和’1’两种字符组成的字符串。
小红可以进行任意次以下操作:
选择字符串的一个字符,将其取反(’0’变’1’或者’1’变’0’)。 小红定义一个01串为好串,当且仅当该01串不包含”010″子串和”101″子串。
例如,”1001″是好串,但”100100″则不是好串。
小红想知道,自己最少操作多少次可以将给定字符串变成好串?
微信:btc9767
TELEGRAM :https://t.me/btcok9
具体资料介绍
web3的一级市场千万收益的逻辑
进群点我
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台-javagopython毕设 » 小红拿到了一个01串。所谓01串,指仅由’0’和’1’两种字符组成的字符串。
小红可以进行任意次以下操作:
选择字符串的一个字符,将其取反(’0’变’1’或者’1’变’0’)。 小红定义一个01串为好串,当且仅当该01串不包含”010″子串和”101″子串。
例如,”1001″是好串,但”100100″则不是好串。
小红想知道,自己最少操作多少次可以将给定字符串变成好串?
进群点我
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台-javagopython毕设 » 小红拿到了一个01串。所谓01串,指仅由’0’和’1’两种字符组成的字符串。
小红可以进行任意次以下操作:
选择字符串的一个字符,将其取反(’0’变’1’或者’1’变’0’)。 小红定义一个01串为好串,当且仅当该01串不包含”010″子串和”101″子串。
例如,”1001″是好串,但”100100″则不是好串。
小红想知道,自己最少操作多少次可以将给定字符串变成好串?
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台-javagopython毕设 » 小红拿到了一个01串。所谓01串,指仅由’0’和’1’两种字符组成的字符串。 小红可以进行任意次以下操作: 选择字符串的一个字符,将其取反(’0’变’1’或者’1’变’0’)。 小红定义一个01串为好串,当且仅当该01串不包含”010″子串和”101″子串。 例如,”1001″是好串,但”100100″则不是好串。 小红想知道,自己最少操作多少次可以将给定字符串变成好串?