剑指Offer题目笔记27（动态规划单序列问题）

面试题89：

问题：

​ 输入一个数组表示某条街道上的一排房屋内财产的数量。相邻两栋房屋不能同时被盗，问小偷能偷取到的最多财物。

解决方案一（带缓存的递归）：

解决方案：

1. 由于有报警系统，小偷不能同时偷相邻两栋房屋，故小偷在到达标号为i的房屋时他能偷取的财物的最大值，即f（i）=max（f（i-2）+nums[i]，f（i-1））。
2. 创建一个数组dp，它的第i个元素dp[i]用来保存f（i）的结果。如果f（i）之前已经计算出结果，那么只需要从数组dp中读取dp[i]的值，不用再重复计算。如果之前从来没有计算过，则根据状态转移方程递归计算。

源代码：

class Solution {public int rob(int[] nums) {int[] dp = new int[nums.length];//将dp数组的所有值赋值为-1Arrays.fill(dp,-1);dfs(nums,nums.length-1,dp);return dp[nums.length-1];}private void dfs(int[] nums,int len,int[] dp){if(len == 0){dp[len] = nums[0];}else if(len == 1){dp[len] = Math.max(nums[0],nums[1]);}else if(dp[len] < 0){dfs(nums,len-1,dp);dfs(nums,len-2,dp);dp[len] = Math.max(dp[len-1],dp[len-2] + nums[len]);}}
}

解决方案二：（空间复杂度为O（n）的迭代）：

解决方案：

​ 由下到上，先求出f（0）和f（1）的值，再通过状态转移方程f（i） = Math,max(f（i-1），f（i-2） + nums[i])求出f（2）以此类推求得f（i）。

源代码：

class Solution {public int rob(int[] nums) {int len = nums.length;int[] dp = new int[len];dp[0] = nums[0];if(len >= 2){dp[1] = Math.max(nums[1],nums[0]);}for(int i = 2;i < len;i++){dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i]);}return dp[len-1];}
}

解决方案三：（空间复杂度为O（1）的迭代）：

解决方案：

​ 观察上述代码，就能发现计算“dp[i]”时只需要用到“dp[i-1]”和“dp[i-2]”这两个值，也就是说，只需要缓存两个值就足够了，并不需要一个长度为n的数组。

源代码：

class Solution {public int rob(int[] nums) {int len = nums.length;int[] dp = new int[2];dp[0] = nums[0];if(len >= 2){dp[1] = Math.max(nums[0],nums[1]);}for(int i = 2;i < len;i++){dp[i % 2] = Math.max(dp[(i-1) % 2],dp[(i-2) % 2 ] + nums[i]);}return dp[(len - 1) % 2];}
}

解决方案四：（使用两个状态转移方程）：

解决方案：

​ 由于小偷到达标记为i的房屋是有两个选择，他进去偷东西和不进去偷东西，定义f（i）为不进去偷东西，g（i）为进去偷东西，因此f（i）= max（f（i-1），g（i-1）），g（i） = f（i-1） + nums[1]。这两个状态转移方程有隐含条件i必须大于0，不然i-1没有意义，因此f（0）= 0，g（0） = nums[0]。

源代码：

class Solution {public int rob(int[] nums) {int len = nums.length;int[][] dp = new int[2][2];//dp【0】为f（i）dp[0][0] = 0;//dp【1】为g（i）dp[1][0] = nums[0];for(int i = 1;i < len;i++){dp[0][i % 2] = Math.max(dp[0][(i - 1) % 2],dp[1][(i - 1) % 2]);dp[1][i % 2] = Math.max(dp[0][i % 2],dp[0][(i-1) % 2] + nums[i]);}return Math.max(dp[0][(len - 1) % 2],dp[1][(len - 1) % 2]);}
}

面试题90：

问题：

​ 一条环形街道上有若干房屋，输入一个数组表示该条街道上的房屋内财产的数量，计算小偷在这条街道上最多能偷取到的财产数量。

解决方案：

1. 如果小偷去偷标号为0的房屋，那么他就不能去偷标号为n-1的房屋；如果小偷去偷标号为n-1的房屋，那么他就不能去标号为0的房屋。
2. 可以将这个问题分解成两个子问题：一个问题是求小偷从标号为0开始到标号为n-2结束的房屋内能偷得的最多财物数量，另一个问题是求小偷从标号为1开始到标号为n-1结束的房屋内能偷得的最多财物数量。

源代码：

class Solution {public int rob(int[] nums) {int len = nums.length;if(len == 0){return 0;}if(len == 1){return nums[0];}//0~n-2int result1 = dfs(nums,0,len-2);//1~n-1int result2 = dfs(nums,1,len-1);return Math.max(result1,result2);}private int dfs(int[] nums,int start,int end){int[] dp = new int[2];dp[0] = nums[start];if(start < end){dp[1] = Math.max(nums[start],nums[start+1]);}for(int i = start+2;i <= end;i++){int j = i - start;dp[j % 2] = Math.max(dp[(j-1) % 2],dp[(j-2) % 2] + nums[i]); }return Math.max(dp[0],dp[1]);}
}

面试题91：

问题：

​ 一排n幢房子要粉刷成红色、绿色和蓝色，不同房子被粉刷成不同颜色的成本不同。要求任意相邻的两幢房子的颜色都不一样。

解决方案：

1. 当计算粉刷标记为i的房子时的成本，得先考虑标记i-1的房子的颜色。因此，需要3个表达式，r（i）表示粉刷红色、g（i）表示粉刷绿色、b（i）表示粉刷蓝色。
2. 如果标记i的房子粉刷红色时，那么标记i-1的房子可以被粉刷为绿色或蓝色，r（i） = min（g（i-1），b（i-1））+ costs[i]。如果标记i的房子粉刷绿色时，那么标记i-1的房子可以被粉刷为红色或蓝色，g（i） = min（r（i-1），b（i-1））+ costs[i]。如果标记i的房子粉刷蓝色时，那么标记i-1的房子可以被粉刷为绿色或红色，b（i） = min（g（i-1），r（i-1））+ costs[i]。

源代码：

class Solution {public int minCost(int[][] costs) {int len = costs.length;//将三个一维数组合成为一个二维数组int[][] dp = new int[3][2];for(int i = 0;i < 3;i++){dp[i][0] = costs[0][i];}for(int i = 1;i < len;i++){for(int j = 0;j < 3;j++){//计算另外两种颜色的成本int result1 = dp[(j + 1) % 3][(i - 1) % 2];int result2 = dp[(j + 2) % 3][(i - 1) % 2];dp[j][i % 2] = Math.min(result1,result2) + costs[i][j];}}int last = (len-1) % 2;return Math.min(Math.min(dp[0][last],dp[1][last]),dp[2][last]);}
}

面试题92：

问题：

​ 输入一个只包含‘0’和‘1’的字符串，至少需要翻转几个字符，才可以使翻转之后的字符串中所有的‘0’位于‘1’的前面。

解决方案：

1. 由于翻转下标为i的字符依赖于前i个字符翻转之后的最后一个字符是‘0’还是‘1’，因此要分两种情况讨论，假设f（i）是翻转之后最后一个字符为0的函数，g（i）为翻转之后最后一个字符为1的函数。
2. 如果下标为i的字符是‘0’，那么f（i）= f（i-1）不需要进行翻转；如果下标为i的字符是‘1’，那么f（i） = f（i-1）+ 1。如果下标为i的字符是‘0’，那么g（i） = min（f（i-1），g（i-1））+ 1，因为当我们将下标为i的字符翻转为‘1’时，那么不管下标i-1的字符是0或1都可以；如果下标为i的字符是‘1’，那么g（i）= min（f（i-1），g（i-1）），因为下标为i的字符已经为‘1’了，不需要翻转。

源代码：

class Solution {public int minFlipsMonoIncr(String s) {int len = s.length();int[][] dp = new int[2][2];char ch = s.charAt(0);dp[0][0] = ch == '0'?0:1;dp[1][0] = ch == '0'?1:0;for(int i = 1;i < len;i++){char sh = s.charAt(i);int result1 = dp[0][(i - 1) % 2];int result2 = dp[1][(i - 1) % 2];dp[0][i % 2] = result1 + (sh == '0'?0:1);dp[1][i % 2] = Math.min(result1,result2) + (sh == '1'?0:1); }return Math.min(dp[0][(len - 1) % 2],dp[1][(len - 1) % 2]);}
}

面试题93：

问题：

​ 输入一个没有重复数字的单调递增的数组，数组中至少有3个数字，请问数组中最长的斐波那契数列的长度是多少。

解决方案：

1. 将数组记为A，A[i]表示数组中下标为i的数字。对于每个j（0≤j＜i），A[j]都有可能是在某个斐波那契数列中A[i]前面的一个数字。如果存在一个k（0≤k＜ j）满足A[k]+A[j]=A[i]，那么这3个数字就组成了一个斐波那契数列。这个以A[i]为结尾、前一个数字是A[j]的斐波那契数列是在以A[j]为结尾、前一个数字是A[k]的序列的基础上增加一个数字A[i]，因此前者的长度是在后者的长度的基础上加1。
2. 由于状态转移方程有两个参数i和j，因此需要一个二维数组来缓存f（i，j）的计算结果。i对应二维数组的行号，j对应二维数组的列号。由于i大于j，因此实际上只用到了二维数组的左下角部分。如果数组的长度是n，那么i的取值范围为1～n-1，而j的取值范围为0～n-2。

源代码：

class Solution {public int lenLongestFibSubseq(int[] arr) {int len = arr.length;//使用map数组记录每个数字在数组中的下标Map<Integer,Integer> map = new HashMap<>();for(int i = 0;i < len;i++){map.put(arr[i],i);}int[][] dp = new int[len][len];int result = 2;for(int i = 1;i < len;i++){for(int j = 0;j < i;j++){//判断数组中是否存在一个数字 arr[k]满足arr[k]=arr[i]-arr[j]。int k = map.getOrDefault(arr[i]-arr[j],-1);//如果存在，就在f（j，k）的基础上加一dp[i][j] = k >= 0 && k < j?dp[j][k] + 1:2;result = Math.max(result,dp[i][j]);}}return result > 2?result:0;}
}

面试题94：

问题：

​ 输入一个字符串，请问至少需要分割几次才可以使分割出的每个字符串都是回文。

解决方案：

1. 假设字符串为S，下标为i的字符为S[i]，下标从j到i的子字符串为S[j…i]。用 f（i）表示从下标为0到i的子字符串S[0…i]的符合条件的最少分割次数。如果字符串的长度是n，那么f（n-1）就是问题的解。
2. 如果子字符串S[0…i]本身就是一个回文，那么不需要分割就符合要求，此时f（i）等于0。如果子字符串S[0…i]不是一个回文，那么对每个下标j（1≤j≤i）逐一判断子字符串S[j…i]是不是回文。如果是回文，那么这就是一个有效的分割方法，此时的分割次数相当于子字符串S[0…j-1]的分割次数再加1，因为这是将子字符串S[0…j-1]按照要求分割之后再在S[j-1]和S[j]这两个字符中间再分割一次。因此，f（i）就是所有符合条件的j对应的f（j-1）的最小值加1。

源代码：

class Solution {public int minCut(String s) {int len = s.length();//使用二维数组记录j到i是否回文boolean[][] flag = new boolean[len][len];for(int i = 0;i < len;i++){for(int j = 0;j <= i;j++){char ch1 = s.charAt(i);char ch2 = s.charAt(j);//i <= j+1用于判断i和j相邻的情况、flag[j+1][i-1]用于判断j到i不相邻的情况if(ch1 == ch2 && (i <= j+1 || flag[j+1][i-1])){flag[j][i] = true;}}}int[] dp = new int[len];for(int i = 0;i < len;i++){//如果0到i是回文数，那么就不需要分割if(flag[0][i]){dp[i] = 0;}else{//先做最坏的打算，字符需要分割成一个一个的字符。例如abcd，就需要分割3次dp[i] = i;for(int j = 1;j <= i;j++){//如果j到i是回文数，那么就在dp【j-1】切割次数的基础上加一if(flag[j][i]){dp[i] = Math.min(dp[i],dp[j-1] + 1);}}}}return dp[len-1];}
}