LC926. 将字符串翻转到单调递增(JAVA - 动态规划)

题目描述

难度 - 中等
LC926. 将字符串翻转到单调递增(JAVA - 动态规划)

如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是 单调递增 的。
给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。
返回使 s 单调递增的最小翻转次数。

示例 1：
输入：s = “00110”
输出：1
解释：翻转最后一位得到 00111.

示例 2：
输入：s = “010110”
输出：2
解释：翻转得到 011111，或者是 000111。

示例 3：
输入：s = “00011000”
输出：2
解释：翻转得到 00000000。

提示：
1 <= s.length <= 10^5
s[i] 为 ‘0’ 或 ‘1’

动态规划

单调递增的字符串满足以下性质：
1.首个字符是 0 或 1；
2.其余的每个字符，字符 0 前面的相邻字符一定是 0，字符 1 前面的相邻字符可以是 0 或 1。

我们用动态规划去解答这个题时，每个位置我们都要考虑，其变成0或者1，的情况，最后我们取改变最小的值，

当 1≤i<n 时，考虑下标 i 处的字符。如果下标 i 处的字符是 0，则只有当下标 i−1 处的字符是 0 时才符合单调递增；如果下标 i 处的字符是 1，则下标 i−1 处的字符是 0 或 1 都符合单调递增，此时为了将翻转次数最小化，应分别考虑下标 i−1 处的字符是 0 和 1 的情况下需要的翻转次数，取两者的最小值。

代码演示：

class Solution {public int minFlipsMonoIncr(String s) {int n = s.length();int dp0 = 0;int dp1 = 1;for(int i = 0; i < n;i++){char c = s.charAt(i);int newDp0 = dp0;int newDp1 = Math.min(dp0,dp1);if(c == '1'){newDp0++;}else{newDp1++;}dp0 = newDp0;dp1 = newDp1;}return Math.min(dp0,dp1);}}