剑指 Offer II 092. 翻转字符【中等题】
思路：【动态规划】
二阶dp数组
dp[i][0]表示将第i位翻转为0后，数组保持递增的最小翻转次数
dp[i][1]表示将第i位翻转为1后，数组保持递增的最小翻转次数
初始状态：
dp[0][0] = s.charAt(0) == '0' ? 0 : 1
dp[0][1] = s.charAt(0) == '1' ? 0 : 1
转移方程：
dp[i][0] = dp[i-1][0]+s.charAt(i) == '0' ? 0:1
dp[i][1] = Math.min(dp[i-1][0],dp[i-1][1])+s.charAt(i) == '1' ? 0:1
代码：【dp数组】
class Solution {
public int minFlipsMonoIncr(String s) {
//动态规划解题
int n = s.length();
//dp二维数组
// dp[i][0]表示将第i位翻转为0时，使字符串s单调递增的最小翻转次数，此时i-1处的字符必须为0
// dp[i][1]表示将第i位翻转为1时，使字符串s单调递增的最小翻转次数，此时i-1处的字符可以为0也可以为1
int[][] dp = new int[n][2];
dp[0][0] = s.charAt(0) == '0' ? 0 : 1;//第0位字符为0,则dp[0][0]=0,否则为1
dp[0][1] = s.charAt(0) == '1' ? 0 : 1;//第0位字符为1,则dp[0][1]=0,否则为1
for (int i = 1; i < n; i++) {
int k1 = 0,k2 = 0;
if (s.charAt(i) == '0'){
k2++;
}else {
k1++;
}
//将第i位翻转为0的最小翻转次数 为 dp[i-1][0] + (s[i] == ‘1’ ？ 1 ： 0)
dp[i][0] = dp[i-1][0] + k1;
//将第i位翻转为1的最小翻转次数 为 Math.min(dp[i-1][0],dp[i-1[1]) + (s[i] == '0' ? 1 : 0)
dp[i][1] = Math.min(dp[i-1][0],dp[i-1][1]) + k2;
}
//最后返回将第n-1位翻转为0或者翻转为1的较小值
return Math.min(dp[n-1][0],dp[n-1][1]);
}
}
代码：【滚动数组】
class Solution {
public int minFlipsMonoIncr(String s) {
//动态规划解题
int n = s.length();
//滚动数组模拟dp数组
// dp0表示将第i位翻转为0时，使字符串s单调递增的最小翻转次数，此时i-1处的字符必须为0
// dp1表示将第i位翻转为1时，使字符串s单调递增的最小翻转次数，此时i-1处的字符可以为0也可以为1
int dp0 = s.charAt(0) == '0' ? 0 : 1;//第0位字符为0,则dp[0][0]=0,否则为1
int dp1 = s.charAt(0) == '1' ? 0 : 1;//第0位字符为1,则dp[0][1]=0,否则为1
for (int i = 1; i < n; i++) {
int k1 = 0,k2 = 0;
if (s.charAt(i) == '0'){
k2++;
}else {
k1++;
}
//将第i位翻转为0的最小翻转次数 为 dp[i-1][0] + (s[i] == ‘1’ ？ 1 ： 0)
k1 += dp0;
//将第i位翻转为1的最小翻转次数 为 Math.min(dp[i-1][0],dp[i-1[1]) + (s[i] == '0' ? 1 : 0)
k2 += Math.min(dp0,dp1);
dp0 = k1;
dp1 = k2;
}
//最后返回将第n-1位翻转为0或者翻转为1的较小值
return Math.min(dp0,dp1);
}
}
剑指 Offer II 093. 最长斐波那契数列【中等题】
思路：【动态规划】【双指针】
参考题解
动态规划+双指针，就是快！
代码：
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n = arr.length,max = 0;
//dp[i][j]为arr数组中以下标 i j 位置的数字为结尾的合法斐波那契数列，dp[i][j]的值表示所表示的斐波那契数列的长度
int[][] dp = new int[n][n];
//遍历数组，以遍历到的数字arr[k]为目标合法斐波那契数列子序列的结束位置
for (int k = 2; k < n; k++) {
//定义双指针 i 和 j 其中 i表示目标合法斐波那契数列子序列的起始位置，初值为 0，j表示目标合法斐波那契数列子序列结束位置的前一位，初值为 k-1
int i = 0, j = k-1;
//当 i < j 时，在[i,j]窗口内筛选是否存在 目标合法斐波那契数列子序列
while (i < j){
//当 arr[i] + arr[j] == arr[k]时，说明找到了一个以 j k 位置数字结束的合法斐波那契数列（这里简写为jk目标）
if (arr[i] + arr[j] == arr[k]){
//如果 dp[i][j] == 0 表示以 i j 位置数字结束的所有子序列无法构成合法斐波那契数列，所以 jk目标的长度只能是 3
if (dp[i][j] == 0){
dp[j][k] = 3;
}else {
//否则 jk目标的长度等于 ij目标的长度+1 与 jk目标的长度 两者之间的最大值
dp[j][k] = Math.max(dp[i][j]+1,dp[j][k]);
}
//此时更新max为 max 和 jk目标长度 两者之间的最大值
max = Math.max(max,dp[j][k]);
//i指针右移 j指针左移 继续在窗口内寻找合法斐波那契数列子序列
i++;
j--;
}else if (arr[i] + arr[j] < arr[k]){
//当 arr[i] + arr[j] < arr[k]时，根据arr递增的这一性质，为了使 arr[i] + arr[j] ==> arr[k],我们应该尝试右移i，然后重新判断
i++;
}else {
//当 arr[i] + arr[j] > arr[k]时，根据arr递增的这一性质，为了使 arr[i] + arr[j] ==> arr[k],我们应该尝试左移j，然后重新判断
j--;
}
}
}
//程序执行过程中，max保持始终是 合法斐波那契数列长度的最大值，因此根据题意程序结束时返回max即可
return max;
}
}