小红拿到了一个 01 串，她准备将若干个字符'1' 染成红色，将若干个字符'0' 染成蓝色，但有个限制：如果一个'0' 和一个'1' 相邻，那么它们不能同时染色。
小红想知道，最多可以染多少个字符？
输入描述输入仅有一行，为小红拿到的 01 串。
字符串长度不超过200000。
输出描述一个正整数，代表能染色的最多字符。
示例一 输入 110011 输出 4 说明染红第一个、第三个、第五个、第六个字符即可。
解题思路每一个位置都有染和不染两种情况，故可以用状态dp来解决问题。
也可以贪心地解决问题，因为对于每一个01或10子串，只能染色一个字符，因此可以通过字符串中01或10子串的个数来进行计算。
代码 解法一：DP Python # 题目：【DP】字节跳动2023秋招-小红的 01 串# 作者：闭着眼睛学数理化# 算法：状态DP# 代码有看不懂的地方请直接在群上提问s = input()n = len(s)# 初始化n*2的二维dp数组# dp[i]表示考虑第i个字符的情况# dp[i][0]表示第i个字符染色，能得到的最多染色数目# dp[i][1]表示第i个字符不染，能得到的最多染色数目dp = [[0, 0] for _ in range(n)]# 对第0个字符进行染色dp[0][0] = 1for i in range(1, n):# 如果第i个字符和第i-1个字符不同# 两种情况：# 1. 当前字符染色，前一个字符不染# 2. 当前字符不染，前一个字符可以染色也可以不染色if s[i] != s[i-1]:# 当前字符染色，+1表示当前字符染色后，染色数目+1dp[i][0] = dp[i-1][1] + 1# 当前字符不染色，为上一个字符染色或不染取得的最大值dp[i][1] = max(dp[i-1][0], dp[i-1][1])# 如果第i个字符和第i-1个字符相同# 两种情况：# 1. 当前字符染色，前一个字符可以染色也可以不染色# 2. 当前字符不染，前一个字符可以染色也可以不染色else:dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + 1dp[i][1] = max(dp[i-1][0], dp[i-1][1])print(max(dp[-1])) Java import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String s = scanner.nextLine();int n = s.length();int[][] dp = new int[n][2];dp[0][0] = 1;for (int i = 1; i < n; i++) {if (s.charAt(i) != s.charAt(i - 1)) {dp[i][0] = dp[i - 1][1] + 1;dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);} else {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]) + 1;dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);}}int maxColoring = Math.max(dp[n - 1][0], dp[n - 1][1]);System.out.println(maxColoring);}} C++ #include #include #include using namespace std;int main() {string s;cin >> s;int n = s.length();vector dp(n, vector(2, 0));dp[0][0] = 1;for (int i = 1; i < n; i++) {if (s[i] != s[i - 1]) {dp[i][0] = dp[i - 1][1] + 1;dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]);} else {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + 1;dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]);}}int maxColoring = max(dp[n - 1][0], dp[n - 1][1]);cout