题目内容

小塔的游戏有一个长度为$k$且只包含字符$0$和$1$字符串，下标为$1$到$k$。

定义其权值为：每次操作可以选择一个下标$i$($1≤i≤k$)，将[$1,i$]的字符全部取反($0$变$1$,$1$变$0$)。将字符串变为全$1$的最少操作次数。

例如字符串$00110$，第一次操作选择$i=5$，字符串变成$11001$，第二次操作选择$i=4$，字符串变成$00111$，第三次操作选择$i=2$，字符串变成$11111$。至少需要$3$次操作，字符串权值为$3$。

思路

  此题是一个三维动态规划问题，只要想到了状态如何表示，那么状态之间的转移其实是比较简单的，首先这里对于字符串的操作其实就是选定字符串的一个前缀将前缀里的1与0全部翻转，在只有这种操作下，我们要将一个字符串变为全1最小的操作次数其实就是从右往左，只要碰到0就将其翻转，选定的前缀逐渐变小，这是一个贪心的操作，也是最优，这是解题的基础

  设置dp[i][j][k]，定义为以下表i结尾，长度为奇或偶，权值为奇或偶的子字符串的个数，0表示偶，1表示奇，状态转移分三种情况

1. 当前位为1，无需操作，直接从前一位的奇偶状态转移
2. 当前位为0但与前一位一致，同样无需额外操作，直接从前一位的奇偶状态转移
3. 当前位为0但与前一位不一致，此处需要两次操作（使此处变1后前一位在操作一次使前面的位数回到原来状态），奇偶状态不变转移

（从状态转移规律可以进行思考，其实可以得出一个结论，以1开头的字符串权值一定为偶，以0开头的字符串权值一定为奇，至于结论如何得来，可以仔细思考思考）

代码