给定一个只包含’0’和’1’两种字符的字符串，每次操作可以选择相邻的两个字符，将它们同时变成’0’或者同时变成’1’。 请问最少多少次操作后，所有的字符都相同？ 字符串长度不超过1000。
区块链毕设网qklbishe.com为您提供问题的解答
给定一个只包含’0’和’1’两种字符的字符串，每次操作可以选择相邻的两个字符，将它们同时变成’0’或者同时变成’1’。
请问最少多少次操作后，所有的字符都相同？
字符串长度不超过1000。
熟悉的dp问题，但是要两个dp数组。转移方程：当str[i] == ‘1’时，dp0[i] = min(dp0[i-1],dp0[i-2])+1;dp1[i] = dp1[i-1]。
意思就是当第i位不为0时，dp0[i]的值要么是对前两位进行变换，要么是对前一位进行变化，然后取最小+1；
而对于dp1[i]来说，因为str[i]就是‘1’所以值可以与前一位相同不需要变换。反之等于’0’的情况亦然。
最后返回值为dp0[n-1],dp1[n-1]的较小值。
注意初始条件哦。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param str string字符串 * @return int整型 */ int minOperations(string str) { // write code here int n = str.size(); if(n == 0 || n == 1)return 0; if(n == 2)return str[0] == str[1]?0:1; vector<int>dp0(n,0); vector<int>dp1(n,0); if(str[0] == str[1]){ if(str[0] == '0'){ dp1[0]= 1; dp1[1]= 1; } else{ dp0[0]=1; dp0[1]=1; } } else{ if(str[0] == '0'){ dp0[1]=1; dp1[0]=1; dp1[1]=1; }else{ dp1[1]=1; dp0[0]=1; dp0[1]=1; } } for(int i =2;i<n;++i){ if(str[i] == '0'){ dp1[i] = min(dp1[i-1],dp1[i-2])+1; dp0[i] = dp0[i-1]; }else{ dp0[i] = min(dp0[i-1],dp0[i-2])+1; dp1[i] = dp1[i-1]; } } return min(dp0[n-1],dp1[n-1]); } };
27:47
以上就是关于问题给定一个只包含’0’和’1’两种字符的字符串，每次操作可以选择相邻的两个字符，将它们同时变成’0’或者同时变成’1’。
请问最少多少次操作后，所有的字符都相同？
字符串长度不超过1000。的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
.jpg){kind=link}