题解 | #小美的01串翻转#

题解一（枚举）

枚举所有起点开始的子串，求出以 0 开头或以 1 开头的最小权值，并累加到结果中。

写法 1：

fun main(args: Array<String>) {
    val str = nextString()
    var ret = 0
    for (i in 0 until str.length) {
        var c0 = 0
        var c1 = 0
        for (j in i until str.length) {
            if ((str[j] == '0' && (j - i) % 2 == 0) || (str[j] == '1' && (j - i) % 2 == 1)) {
                c0++
            } else {
                c1++
            }
            ret += min(c0, c1)
        }
    }
    println(ret)
    done()
}

写法 2：

fun main(args: Array<String>) {
    val str = nextString()
    var ret = 0
    for (i in 0 until str.length) {
        var c0 = 0
        var c1 = 0
        for (j in i until str.length) {
            c0 += if (str[j] == "01"[(j - i) % 2]) 1 else 0
            c1 += if (str[j] == "10"[(j - i) % 2]) 1 else 0
            ret += min(c0, c1)
        }
    }
    println(ret)
    done()
}

复杂度分析：

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

题解二（区间 DP）

• 定义： 定义 dp[i][j] 表示区间 [i, j] 的最小权值，考虑到以 0 或 1 开头的权值可能不同，再增加第三维度 [k] 表示以 0 和 1 结尾的最小权值；
• 转移： 对于 [i, j] 区间来说，可以从 [i, j - 1] 区间转移过来，对于字符 str[j] 来说，有转换和不转换两种选择，那么有：
  • 转换：dp[i][j][x xor 1] = dp[i][j - 1][x] + 1
  • 不转换：dp[i][j][x] = dp[i][j - 1][x xor 1]

fun main(args: Array<String>) {
    val str = nextString()
    val n = str.length
    var ret = 0
    // dp[i][j][2] 表示 [i,j] 以 0 和 1 结尾的最小权值
    val dp = Array(n) { Array(n) { IntArray(2) } }
    for (i in 0 until n) {
        dp[i][i][0] = if (str[i] == '0') 0 else 1
        dp[i][i][1] = if (str[i] == '0') 1 else 0
    }
    for (len in 2..n) {
        for (i in 0..n - len) {
            val j = i + len - 1
            val x = str[j] - '0'
            dp[i][j][x] = dp[i][j - 1][x xor 1]
            dp[i][j][x xor 1] = dp[i][j - 1][x] + 1
            // println("len=$len, i=$i, j=$j, x=$x, sub=${str.substring(i, j + 1)} ${dp[i][j][x]}, ${dp[i][j][x xor 1]}")
            ret += Math.min(dp[i][j][x], dp[i][j][x xor 1])
        }
    }
    println(ret)
    done()
}

复杂度分析：

• 时间复杂度：O(n^2) 一共有 n^2 个子状态，每个子状态的时间是 O(1)，动态规划整体时间复杂度是 O(n^2)；
• 空间复杂度：O(n^2) DP 数组空间。