1 分析

首先，给定一个字符串 s, 当小美执行完最少的操作次数后，目标字符串的形式要么是target = "101010..."，要么是target = "010101..."。

例如，对于字符串 s = "10001"，经过一次操作（中间的 0 -> 1）后，目标字符串为 "target = "10101""，这既是上述的第一种目标字符串形式。

因此，我们可以初始化两个和输入字符串长度相同的两种可能目标字符串，对于上例，初始化的目标字符串为 s1 = "10101", s2 = "01010"，然后将每一个子串分别与s1 和 s2对比，不同字符的个数既是所需要的操作数，对于例子，与s1不同字符的个数count1 = 1， 与s2不同字符的个数count2 = 4, 最后取 min(count1, count2) 即是输入字符串s01翻转所需的最小操作数（权值）。

对于该题，可以将输入字符串s的每一个非空子串都与可能的目标字符串target比对求出每个非空字串的权值，然后分别相加既是所有非空子串的权值和。但是使用这种暴力解法的话会超时，因此需要我们进一步思考，简化算法流程。

为便于理解，首先，我们画个表table来表示输入字符串s = “10001”的各个非空子串的权值。

	1	0	0	0	1
	0	1	2	3	4
0		0	1	1	1
1			1	1	1
2				1	1
3					0
4

上表中，table(i,j)表示输入字符s的子串s[i:j]的权值，如table(0, 2) = 1 表示s[0:2] = "100"的权值。

通过观察这张表，可以发现暴力解法存在重复的计算过程，举个例子，比如在计算s的子串 subs = "1000"的权值时，我们已经计算过subs的子串subsubs = "100"的权值，这就造成了一种计算资源的浪费。如果我们把subsubs = "100"的权值计算完后保存了下来，这里为1， 那么，当我们遇到字符串 subs = "1000"时，只需要比较最后多出来的一位是否与可能的目标字符串相同即可，如果相等，则subs = "1000"的权值为subsubs = "100"的权值 +1，否则等于subsubs = "100"的权值。

进一步考虑，因为给定字符串s的目标字符串可能是0101..或1010...的形式，我们事先并不知道，因此，我们需要保存字符串s两种可能目标字符串的权值。

具体做法为：

• 1 给定输入字符串 s，初始化两种可能的目标字符串s1="1010..."和s2="0101..."；
• 2 初始化一个存储s不同起始点开始包含的子串的可能权值 vector<vector<int>> nums(n, vector<int>(2, 0))[^1],n=s.length();
• 3 按输入字符的起始索引开始遍历求解当前起始索引的所有子串的权值和

以上面的表为例,输入为s="10001"，具体的执行过程为：

• 1 初始化，目标子串 s1 = "10101", s2= "01010";
• 2 初始化， vector<vector<int>> nums(n, vector<int>(2, 0))
• 3 计算（伪代码）,首先，字符起始索引为 0，

  s = "10001";
  s1 = "10101";
  s2 = "01010";
  res = 0;
  /*从上表可以看出，
  以0为起始索引的字符字串包括：
  10，100，1000，10001*/
  for i = 0 to 4 {
  for j = i to (i+j < n) {
  /*然后开始与可能目标子串对比*/
  if (s[j] != s1[j]) nums[i][0]++;
  if (s[j] != s2[j]) nums[i][1]++;
  res += min(nums[i][0], nums[i][1]);
  }
  }

在上面的伪代码中，每计算完一个子串的权值，res需要及时累加权值和，思考一下，如果res += min(nums[i][0], nums[i][1])放在第一个for的外面会是什么样的计算结果呢 ？

[^1]: nums[i][0] 计算的是字符串s第个位置开始的子串对应目标字符串"1010..."的权值，nums[i][1] 计算的则是对应目标字符串"0101..."的权值.

2 代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string s;
    cin >> s;

    int res = 0, n = s.length();
    // s1 101010..., s2 010101...
    string s1 = "", s2 = "";
    vector<vector<int>> nums(n-1, vector<int>(2, 0));
    for (int i = 0; i <= n/2; ++i) {
        s1 += '1'; s1 += '0';
        s2 += '0'; s2 += '1';
    }
    for (int i = 0; i < n -1; ++i) {
        for (int j = i; j < n; ++j) {
            if (s[j] != s1[j]) nums[i][0]++;
            if (s[j] != s2[j]) nums[i][1]++;
            res += min(nums[i][0], nums[i][1]);
        }
    }

    printf("%lld\n", res);
}
// 64 位输出请用 printf("%lld")

#include <iostream>
using namespace std;



int main() {
    /*
     思路：
     最小操作次数的求法
     一个串要么010101要么101010所以最小操作次数就可以通过两次比对来求得

     子串的求法，进行一个遍历吧就

    n^3的时间复杂度，空间复杂度o（n）
     超时！

     2.思路
     子串的最优解与长度+1子串的最优解有关系吗？
     有关系！且结果为最优解或最优解+1
     所以先求长度为2的子串的权值再往外拓展
     
     对于子串（i，j)只需要比对（i，j-1）并进行增加操作 
     比较两个串0101与1010，求出比对最小值即可，随后保存去比较更长子串

    二维数组动态规划？行！我保存各个子串的权值，保存完再一遍遍历求和。
    需要两个数组，否则不能确保当前匹配的是0开头还是1开头。麻烦
    直接用两个变量保存呢？
    若能证明：子串(i,j)是否只用考虑子串（i，j-1）而不用考虑子串(i+1，j)
    首先其相同部分（i+1，j-1）为固定权值为k；
    对相同部分拓展发现无论i，j位置元素如何，再同一比对下最终其权值都会相同，所以可行

    n方时间复杂度
    
    */

    int res = 0;

    //获取输入
    string str;
    cin >> str;

    //由0开始的和由1开始的
    int start0,start1;



    //所有的长度至少为2的子串
    for(int i = 0; i <str.size()-1;i++)
    {
        start0 = 0,start1 = 0;

        //对于start0来说2的整数倍的地方应该为0，对于start1来说为1
        if(i%2==0) (str[i]=='0')?start1++:start0++; 
        else (str[i]=='0')?start0++:start1++;

        for(int j = i + 1; j < str.size();j++)
        {
            if(j%2==0) (str[j]=='0')?start1++:start0++; 
            else (str[j]=='0')?start0++:start1++;
            
            //子串权值求和
            res += (start0>start1)?start1:start0;

        }
    }


    cout<<res;
    return 0;

}

// 64 位输出请用 printf("%lld")

import java.util.*;

public class Main {
    static boolean isAchieved;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] chars = sc.next().toCharArray();
        int n = chars.length;
        int[][][] dp = new int[n][n][2];
        int res = 0;
        dp[0][0][chars[0] - '0'] = 0;
        dp[0][0][1 - chars[0] + '0'] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == 0 && j == 0) continue;
                int bit = chars[j] - '0';
                dp[i][j][bit] = dp[i][j - 1][1 - bit];
                dp[i][j][1 - bit] = dp[i][j - 1][bit] + 1;
                res += Math.min(dp[i][j][bit], dp[i][j][1 - bit]);
            }
        }
        System.out.println(res);
    }
}

strs = input().strip()
n = len(strs)

res = 0
for i in range(n):
    # c0表示当前以i开头的字串，变换后第一个字符为0，需要的变换次数
    # c1表示当前以i开头的字串，变换后第一个字符为1，需要的变换次数
    c0, c1 = 0, 0
    for j in range(i, n):
        if (strs[j] == '1' and (j - i) % 2 == 1)&nbs***bsp;(strs[j] == '0' and (j - i) % 2 == 0):
            c1 += 1
        else:
            c0 += 1
        res += min(c0, c1)
print(res)

python版本

dp思路大差不差，但是优化代码实在是头疼，从超时到刚好，再到快速计算花了好久时间

超时→不超时1500ms

st = list(map(int, input().strip()))
dp = [list(st), [int(i!=1) for i in st]]

res = 0

while len(dp[0])>1:
    dp = [dp[1][:-1], dp[0][:-1]]
    
    for idx, i in enumerate(st[-len(dp[0]):]):
        dp[int(i==0)][idx] += 1

    res += sum([min(i, j) for i, j in zip(dp[0], dp[1])])


print(res)

st = list(map(int, input().strip()))
dp = [st, list(map(int, map(lambda x: x==0, st)))]
addtiton = dp.copy()
res = 0

def dp_add(dp1, dp2):
    return [[x + y for x, y in zip(row1, row2)] for row1, row2 in zip(dp1, dp2)]
     
while len(dp[0])>1:
    addtiton = [addtiton[0][1:], addtiton[1][1:]]
    dp = dp_add([dp[1][:-1], dp[0][:-1]], addtiton)
    res += sum([min(i, j) for i, j in zip(dp[0], dp[1])])

print(res)

import java.util.*;
import java.io.*;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String line = bf.readLine();
        int res=0, n= line.length();
        int[][][] dp = new int[n][n][2];//dp[i][j][m] 数组[i,j]要变成以m结尾的01串，所需的修改次数，m=0/1
        for(int i=0;i<n;i++){
            //len=1
            if(line.charAt(i)=='0'){
                dp[i][i][0]=0;
                dp[i][i][1]=1;
            }
            else{
                dp[i][i][0]=1;
                dp[i][i][1]=0;
            }
            
            for(int j=i+1;j<n;j++){
                dp[i][j][0]= dp[i][j-1][1] + (line.charAt(j)=='0' ? 0 : 1);
                dp[i][j][1]= dp[i][j-1][0] + (line.charAt(j)=='0' ? 1 : 0);
            }
        }

        // for(int i=0;i<n;i++){
        //     for(int j=i;j<n;j++){
        //         System.out.println("dp["+i+"]["+j+"][0]=" + dp[i][j][0]);
        //         System.out.println("dp["+i+"]["+j+"][1]=" + dp[i][j][1]);
        //     }
        // }

        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int curr = Math.min(dp[i][j][0], dp[i][j][1]);
                res +=curr;
            }
        }

        System.out.println(res);


        
    }
}

1、定义两个个数组记录如果全部修改为 0101 或 1010，需要修改的位置，1表示需要修改，0表示不需要修改

let s = "0110";
let zeroList = [0,0,1,1]; // => 0101
let oneList = [1,1,0,0]; // => 1010

2、开始计算两个三个字符时需要修改几个字符

let s = "0110";
let newZeroList = [0,1,2]; // => "01","10","01"
let newOneList = [2,1,0]; // => "10","01","10"

然后遍历 newZeroList 和 newOneList 中同一个位置下较小的数加和就是当前长度的权值。

例如
zOL = [0,1,2]
nOL = [2,1,0]
=>[0,1,0] => 权值为 0+1+0=1

3、循环第二步直到长度为 s.length

第二步的迭代过程（zero为例）

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function () {
    // Write your code here
    while(line = await readline()){
        solu(line);
    }
}()
function solu(str) {
    let list = str.split('').map(_ => _);
    let len = str.length;
    let zeroList = [];
    let oneList = [];
    let bit = 0;
    for (let i = 0;i < len;i++) {
        if (list[i] == bit) {
            zeroList.push(0);
            oneList.push(1);
        } else {
            zeroList.push(1);
            oneList.push(0);
        }
        bit = 1 - bit;
    }
    let newZeroList = [];
    let newOneList = [];
    let sum = 0;
    for (let i = 1;i < len;i++) {
        newZeroList.push(zeroList[i - 1] + zeroList[i]);
        newOneList.push(oneList[i - 1] + oneList[i]);
    }
    sum += calc(newZeroList, newOneList, len - 1);
    for (let p = 2;p < len;p++) {
        for (let i = 0;i < len - p;i++) {
            newZeroList[i] += zeroList[i + p];
            newOneList[i] += oneList[i + p];
        }
        sum += calc(newZeroList, newOneList, len - p);
    }
    console.log(sum);
}
function calc(list1, list2, len) {
    // console.log(list1, list2, len);
    let s = 0;
    for (let i = 0;i < len;i++) {
        s += Math.min(list1[i], list2[i]);
    }
    return s;
}

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // s = 0:  dp[i][j][1] = dp[i][j][0] + 1; dp[i][j][0] = dp[i][j][1];
        // s = 1:  dp[i][j][0] = dp[i][j][1] + 1; dp[i][j][0] = dp[i][j][0];
        String str = in.nextLine();
        int len = str.length();
        int[][][] dpList = new  int[len][len][2];
        for (int i = 0; i < len; i++) {
            if (str.charAt(i) == '0') {
                dpList[i][i][0] = 0;
                dpList[i][i][1] = 1;
            } else {
                dpList[i][i][0] = 1;
                dpList[i][i][1] = 0;
            }
        }
        int sum = 0; 
        for (int i = 0; i < len; i++) {
            for (int j = i + 1 ; j < len; j++) {
                if (str.charAt(j) == '0') {
                    dpList[i][j][0] = dpList[i][j-1][1];
                    dpList[i][j][1] = dpList[i][j-1][0] + 1;
                } else {
                    dpList[i][j][0] = dpList[i][j-1][1] +1 ;
                    dpList[i][j][1] = dpList[i][j-1][0];
                }
                sum += Math.min(dpList[i][j][0], dpList[i][j][1]);
            }
        }
        System.out.println(sum);

    }
}

strs = list(map(int, input()))
n = len(strs)
 
res = 0
for i in range(n):
    # c0表示strs[i:j + 1]字串，以0开头的最少变换次数
    # c0表示strs[i:j + 1]字串，以1开头的最少变换次数
    c0, c1 = 0, 0
    for j in range(i,n):
        length = j - i - 1
        if (not strs[j] and length % 2 == 0)&nbs***bsp;(strs[j] and length % 2 == 1):
            # 以0开头长度为偶数的交替字符串最后一位必须为1
            # 以1开头长度为奇数的交替字符串最后一位必须为0
            c0 += 1
        else:
            c1 += 1
        print(i,j,strs[i:j + 1],c0,c1)
        res += min(c0, c1)
print(res)

        import java.util.Scanner;

        public class Main {

            public static void main(String[] args) {

                Scanner in = new Scanner(System.in);

                String s = in.next();

                int sum = getNum(s);

                System.out.println(sum);

            }

            public static int getNum(String s) {

                int n = s.length();

                StringBuffer sb1 = new StringBuffer();

                StringBuffer sb2 = new StringBuffer();

                //sb1表示101010101...即以1开头的标准01串

                //sb2表示010101010...即以0开头的标准01串

                for (int i = 0; i < n; i++) {

                    sb1.append((i+1)%2);

                    sb2.append(i%2);

                }

                int sum = 0;

                //dp1[i][j]表示s.substring(i,j+1)这个子串根据sb1.substring(i,j+1)得到的权重值

                //dp2[i][j]表示s.substring(i,j+1)这个子串根据sb2.substring(i,j+1)得到的权重值

                //s.substring(i,j+1)这个子串的权重值取dp1[i][j]和dp2[i][j]的最小值

                /**举例：对于1000这个串，根据1010得到的权重是1；根据0101得到的权重是3；最后权重取最小值为1

                 */

                int dp1[][] = new int[n][n];

                int dp2[][] = new int[n][n];

                for (int i = 0; i < n ; i++) {

                    for (int j = i ; j < n; j++) {

                        if (j == i ) {

                            dp1[i][j] = s.charAt(i) == sb1.charAt(i) ? dp1[i][j] : 1;

                            dp2[i][j] = s.charAt(i) == sb2.charAt(i) ? dp2[i][j] : 1;

                            sum = sum + Math.min(dp1[i][j], dp2[i][j]);

                            continue;

                        }

                        dp1[i][j] = dp1[i][j - 1];

                        dp2[i][j] = dp2[i][j - 1];

                        if (s.charAt(j) != sb1.charAt(j)) {

                            dp1[i][j] ++;

                        }

                        if (s.charAt(j) != sb2.charAt(j)) {

                            dp2[i][j] ++;

                        }

                        sum = sum + Math.min(dp1[i][j], dp2[i][j]);

                    }

                }

                return sum;

            }

        }