一个很暴力的想法,在满足单调递增的前提下,使每一位分别取 1 或 0,去看看哪个结果小。
递归函数定义int dp(StringBuilder sb, int ind, int pre)
sb是字符串,ind 是字符串当前位,pre 是字符串前一位(0或1)
dp函数表示:从字符串当前位ind开始到字符串结尾,这样一个子字符串,变为单调递增所需要翻转的最小次数。
因此题目所求就是 dp(sb, 0, 0)
。第0位的前一位为0。
具体递归入口有四种情况,根据前一位是0或1 和 当前位是0或1来讨论,即
当前位为0:
前一位为0:
前一位为1:
当前位为1:
前一位为0:
前一位为1:
一开始递归函数定义不明确,导致无法形成重叠子问题,也就无法用备忘录来优化。
在考虑备忘录优化的时候,需要明确备忘录的每一维分别代表什么。参考了这位大佬的题解Java 递归+二维DP+空间优化。
class Solution {
int[][] memo; // 备忘录
public int minFlipsMonoIncr(String s) {
int n = s.length();
memo = new int[n + 1][2];
for(int[] arr : memo){
Arrays.fill(arr, -1);
}
return dp(s.toCharArray(), 0, 0);
}
int dp(char[] s, int ind, int pre){ // sb是字符串,ind 是字符串当前位,pre 是前一位
if(ind == s.length){ // 到字符串结尾了,需要改变的字符为0,返回值为0
return 0;
}
if(memo[ind][pre] != -1){
return memo[ind][pre];
}
int res = 0;
if(s[ind] == '0'){ // 当前位为0
if(pre == 0){ // 前一位为 0
int a = dp(s, ind + 1, s[ind] - '0'); // 保持0不变
s[ind] = '1';
int b = dp(s, ind + 1, s[ind] - '0'); // 把当前0变为1,翻转次数加一
s[ind] = '0';
res += Math.min(a, b); // 取两者中最小的情况
}else if(pre == 1){ // 前一位为 1
s[ind] = '1';
res += dp(s, ind + 1, s[ind] - '0') + 1; // 前一位为1,当前位为0,必须变成1
s[ind] = '0';
}
}else if(s[ind] == '1'){ // 当前位为1
if(pre == 0){ // 前一位为 0
int a = dp(s, ind + 1, s[ind] - '0'); // 保持1不变
s[ind] = '0';
int b = dp(s, ind + 1, s[ind] - '0') + 1; // 把当前1变为0,翻转次数加一
s[ind] = '1';
res += Math.min(a, b); // 取两者中最小的情况
}else if(pre == 1){
res += dp(s, ind + 1, s[ind] - '0'); // 前一位为1,当前位为1,当前1必须保持不变
}
}
memo[ind][pre] = res;
return res;
}
}
优化后
class Solution {
int[][] memo; // 备忘录
public int minFlipsMonoIncr(String s) {
int n = s.length();
memo = new int[n + 1][2];
for(int[] arr : memo){
Arrays.fill(arr, -1);
}
return dp(s.toCharArray(), 0, 0);
}
int dp(char[] s, int ind, int pre){ // sb是字符串,ind 是字符串当前位,pre 是前一位
if(ind == s.length){ // 到字符串结尾了,需要改变的字符为0,返回值为0
return 0;
}
if(memo[ind][pre] != -1){
return memo[ind][pre];
}
int res = 0;
if(s[ind] == '0'){ // 当前位为0
if(pre == 0){ // 前一位为 0
// 保持0不变;
// 把当前0变为1,翻转次数加一;
// 取两者中较小的情况
res = Math.min(dp(s, ind + 1, 0), dp(s, ind + 1, 1) + 1);
}else if(pre == 1){ // 前一位为 1
res = dp(s, ind + 1, 1) + 1; // 前一位为1,当前位为0,必须变成1
}
}else if(s[ind] == '1'){ // 当前位为1
if(pre == 0){ // 前一位为 0
// 保持1不变;
// 把当前1变为0,翻转次数加一;
// 取两者中较小的情况
res = Math.min(dp(s, ind + 1, 1), dp(s, ind + 1, 0) + 1);
}else if(pre == 1){
res = dp(s, ind + 1, 1); // 前一位为1,当前位为1,当前1必须保持不变
}
}
memo[ind][pre] = res;
return res;
}
}
一开始写的时候有个问题,就是在递归函数的参数中记录结果,递归到边界的时候得到结果,这样就是一个纯递归的思路。并没有转成子问题的形式,因此我后续进行备忘录优化始终无法成功。原因还是递归函数定义有问题。
纯递归的代码
class Solution {
int[][][] memo;
public int minFlipsMonoIncr(String s) {
StringBuilder sb = new StringBuilder(s);
int n = s.length();
memo = new int[n + 1][2][2];
for(int[][] arr : memo){
for(int[] a : arr)
Arrays.fill(a, -1);
}
return dp(sb, 0, 0,0 ,sb.charAt(0) - '0');
}
int dp(StringBuilder sb, int ind, int cnt, int pre, int now){
if(ind == sb.length()){
return cnt;
}
if(memo[ind][pre][now] != -1){
return memo[ind][pre][now];
}
int res = 0;
if(sb.charAt(ind) == '0'){
if(ind - 1 >= 0){
if(sb.charAt(ind - 1) == '0'){
int a = dp(sb, ind + 1, cnt, sb.charAt(ind - 1) - '0',0);
sb.setCharAt(ind, '1');
int b = dp(sb, ind + 1, cnt + 1, sb.charAt(ind - 1) - '0',1);
sb.setCharAt(ind, '0');
res += Math.min(a, b);
}else{
sb.setCharAt(ind, '1');
res += dp(sb, ind + 1, cnt + 1, sb.charAt(ind - 1) - '0',1);
sb.setCharAt(ind, '0');
}
}else{
int a = dp(sb, ind + 1, cnt, 0,0);
sb.setCharAt(ind, '1');
int b = dp(sb, ind + 1, cnt + 1, 0,1);
sb.setCharAt(ind, '0');
res += Math.min(a, b);
}
}else{
if(ind - 1 >= 0){
if(sb.charAt(ind - 1) == '0'){
int a = dp(sb, ind + 1, cnt, sb.charAt(ind - 1) - '0',1);
sb.setCharAt(ind, '0');
int b = dp(sb, ind + 1, cnt + 1, sb.charAt(ind - 1) - '0',0);
sb.setCharAt(ind, '1');
res += Math.min(a, b);
}else{
res += dp(sb, ind + 1, cnt, sb.charAt(ind - 1) - '0',1);
}
}else{
int a = dp(sb, ind + 1, cnt, 0,1);
sb.setCharAt(ind, '0');
int b = dp(sb, ind + 1, cnt + 1, 0,0);
sb.setCharAt(ind, '1');
res += Math.min(a, b);
}
}
memo[ind][pre][now] = res;
return res;
}
}
其中cnt就是最后的结果,这样可以通过数据量小的问题,但数据量大的问题必定会超时,而且无法利用记忆化搜索优化。
不管是不是动态规划问题,首先写出递归的暴力解。如果超时,考虑有没有重叠子问题,此时就要注意递归函数的定义,递归函数的返回值应该是子问题的解。可能一开始结果保存在函数参数中是比较好想的。如果一开始写的递归函数是结果在函数参数里的形式,要考虑将结果定义在返回值中,此时需要明确递归函数的定义。