本文共 730 字，大约阅读时间需要 2 分钟。

一. 题目

1. 题目

   

2. 示例

   

二. 方法一: 暴力法

1. 解题思路

2. 解题代码

   def maxScore(self, s: str) -> int:    count = 0    for index in range(1, len(s)):        num1 = s[0:index].count("0")        num2 = s[index:len(s)].count("1")        if count < num1 + num2:            count = num1 + num2    return count

3. 分析

   时间复杂度: O(n^2)
   空间复杂度: O(1)

三. 方法二: 动态规划

1. 解题思路

   1. 先计算出最初的score(左字符串长度为1, 右侧字符串长度为n-1)
   2. 然后遍历整个字符串, 如果字符为0, score + 1,否则 score-1
   3. 然后之前的score进行比较, 如果比之前的结果大, 就替换
   4. 直到遍历结束即可

2. 解题代码

   def maxScore(self, s: str) -> int:    count = s[0].count("0") + s[1:].count("1")    result = count    for i in range(1, len(s) - 1):        if s[i] == "0":            count += 1        else:            count -= 1        result = max(result, count)    return result

3. 分析

   时间复杂度: O(n)
   空间复杂度: O(1)

转载地址：http://usum.baihongyu.com/