Leetcode 1187. Make Array Strictly Increasing / 1043. Partition Array for Maximum Sum #241
Description
示例模版记录：从记忆化搜索到动态规划
要明确分割子问题和缓存的定义和作用。 前者用来设计DFS，后者用来解决重叠子问题。不要一直套模版导致思维定式了。
还有边界返回值的确认。也要看情况而定。比如No.1416要遍历完成字符串，所以返回1。
注意memo缓存数组要一开始赋值-1，标记未访问，否则如果是0则有可能被误认。
另外，我发现记忆化搜索和动态规划某种意义上都是一种归，所以记忆化搜索中DFS函数一般都是有返回数。
相关题目
- 1312. Minimum Insertion Steps to Make a String Palindrome
- 879. Profitable Schemes
- 1105. Filling Bookcase Shelves
- 1416. Restore The Array
- 1048. Longest String Chain
- 1463. Cherry Pickup II
- 1786. Number of Restricted Paths From First to Last Node
- 1799. Maximize Score After N Operations
- 1140. Stone Game II
- 1406. Stone Game III
- 1547. Minimum Cost to Cut a Stick
- 2707. Extra Characters in a String
1043. Partition Array for Maximum Sum
1043. Partition Array for Maximum Sum
一、记忆化搜索
可以把问题分割成多个子问题。比如对于数组范围dfs(0,n)，按照k范围大小，可以依次求解sum(max[0,0] * 1) + dfs(1,n)、sum(max[0,1] * 2) + dfs(2,n)...最后求出最大值。
同时，观察到这样会产生多个重复计算，所以直接用一维数组缓存记录。
class Solution {
int[] arr;
int k, n;
int[][] maxArr;
int[] memo;
public int maxSumAfterPartitioning(int[] arr, int k) {
this.arr = arr;
this.k = k;
n = arr.length;
maxArr = new int[n][n];
for (int i = 0; i < n; ++i) {
int max = arr[i];
for (int j = i; j < n; ++j) {
max = Math.max(max, arr[j]);
maxArr[i][j] = max;
}
}
memo = new int[n];
return dfs(0);
}
private int dfs(int i) {
if (i == n) return 0;
if (memo[i] != 0) return memo[i];
int max = 0;
for (int j = i; j < n && j < i + k; ++j) {
max = Math.max(max, maxArr[i][j] * (j - i + 1) + dfs(j + 1));
}
return memo[i] = max;
}
}二、动态规划
接着可以从记忆化搜索改进到动态规划。逻辑是反过来的，所以有时候需要倒序遍历。
class Solution {
public int maxSumAfterPartitioning(int[] arr, int k) {
int n = arr.length;
int[] dp = new int[n];
for (int i = 0; i < n; ++i) {
int max = arr[i];
for (int j = i; j >= Math.max(i - k + 1, 0); j--) {
max = Math.max(max, arr[j]);
dp[i] = Math.max(dp[i], (j - 1 >= 0 ? dp[j - 1] : 0) + max * (i - j + 1));
}
}
return dp[n - 1];
}
}1187. Make Array Strictly Increasing
1187. Make Array Strictly Increasing
一、记忆化搜索
我一开始想法也是记忆化搜索，但一直错误。但当我去除缓存后，就能过，但是TLE。所以说明缓存使用错误。
class Solution {
int[] arr1;
int n;
TreeSet<Integer> set;
int[] memo;
public int makeArrayIncreasing(int[] arr1, int[] arr2) {
this.arr1 = arr1;
this.n = arr1.length;
this.set = new TreeSet<>();
for (int i : arr2) {
set.add(i);
}
memo = new int[n];
Arrays.fill(memo, -1);
int res = dfs(0);
return res == Integer.MAX_VALUE ? -1 : res;
}
private int dfs(int i) {
if (i == n) {
return 0;
}
// if (memo[i] != -1) {
// return memo[i];
// }
int res = Integer.MAX_VALUE;
if (i == 0 || arr1[i] > arr1[i - 1]) {
res = Math.min(res, dfs(i + 1));
}
Integer next = i - 1 >= 0 ? set.higher(arr1[i - 1]) : set.first();
if (next != null && (i != 0 || next < arr1[i] )) {
int tmp = arr1[i];
// Integer next2 = set.higher(next);
arr1[i] = next;
int cnt = dfs(i + 1);
if (cnt != Integer.MAX_VALUE) {
res = Math.min(res, cnt + 1);
}
arr1[i] = tmp;
// next = next2;
}
// if (i == 0 || arr1[i] > arr1[i - 1] && (i == n - 1 || arr1[i] < arr1[i + 1])) {
// res = Math.min(res, dfs(i + 1));
// }
// if (i == 0 || arr1[i] > arr1[i - 1]) {
// res = Math.min(res, dfs(i + 1));
// }
memo[i] = res;
return res;
}
}重新想一下子问题的分割，就能发现问题所在了。这类问题同样可以用选或不选的思路。首先从0位置开始，可以选择要替换或者不替换。如果不替换，则要考虑当前值是不是严格大于前一个位置的值arr[i] > arr[i-1](i>0)；否则替换，则直接替换在arr2数组中小于当前值但大于前一位置值的最小值。
那么如何设置缓存解决重叠子问题呢？从子问题开始想，假如[1,5,3,6,7]中替换了arr[1]=2，那么子问题就变成了对于2的[2,n)数组严格递增的替换数量。所以可知，设置Map<Integer, Integer>[] memo表示i位置下对于前一位置元素为j的最小操作数。同时dfs函数中加入参数pre代表前一个位置的元素。
class Solution {
int[] arr1;
int n;
TreeSet<Integer> set;
Map<Integer, Integer>[] memo;
public int makeArrayIncreasing(int[] arr1, int[] arr2) {
this.arr1 = arr1;
this.n = arr1.length;
this.set = new TreeSet<>();
for (int i : arr2) {
set.add(i);
}
this.memo = new HashMap[n];
for (int i = 0; i < n; i++) {
memo[i] = new HashMap<>();
}
int res = dfs(0, -1);
return res == Integer.MAX_VALUE ? -1 : res;
}
private int dfs(int i, int pre) {
if (i == n) {
return 0;
}
if (memo[i].containsKey(pre)) {
return memo[i].get(pre);
}
int res = Integer.MAX_VALUE;
if (i == 0) {
Integer next = set.first();
int cnt = dfs(i + 1, next);
if (cnt != Integer.MAX_VALUE) {
res = Math.min(res, cnt + 1);
}
res = Math.min(res, dfs(i + 1, arr1[0]));
} else {
Integer next = set.higher(pre);
if (next != null) {
int cnt = dfs(i + 1, next);
if (cnt != Integer.MAX_VALUE) {
res = Math.min(res, cnt + 1);
}
}
if (arr1[i] > pre) {
res = Math.min(res, dfs(i + 1, arr1[i]));
}
}
memo[i].put(pre, res);
return res;
}
}1027. Longest Arithmetic Subsequence
1027. Longest Arithmetic Subsequence
这道题直接用递推可以想出来。设Map<Integer, Integer> memo，memo[i]表示0~i范围公差为key数量为value。所以递推方程就是两次遍历求d=nums[i]-nums[j]的最大数量。
class Solution {
public int longestArithSeqLength(int[] nums) {
int n = nums.length;
int res = 1;
Map<Integer, Integer>[] memo = new Map[n];
for (int i = 0; i < n; ++i) {
memo[i] = new HashMap<>();
memo[i].put(nums[i], 1);
for (int j = 0; j < i; ++j) {
int diff = nums[i] - nums[j];
int len = memo[j].getOrDefault(diff, 1) + 1;
memo[i].put(diff, len);
res = Math.max(res, len);
}
}
return res;
}
}那记忆化搜索怎么想呢？一般写法有选或不选和枚举。这里因为每个元素可能有不同的公差，所以用枚举法。
既然是枚举，那么要知道枚举什么。显然是枚举所有以nums[i]结尾的最长等差子序列的长度。令dfs函数返回Map。
class Solution {
int[] nums;
int n;
Map<Integer, Integer>[] memo;
int ans = 1;
public int longestArithSeqLength(int[] nums) {
this.nums = nums;
n = nums.length;
memo = new HashMap[n];
for (int i = 0; i < n; ++i) {
dfs(i);
}
return ans;
}
private Map<Integer, Integer> dfs(int i) {
if (memo[i] != null) {
return memo[i];
}
memo[i] = new HashMap<>();
memo[i].put(nums[i], 1);
for (int j = 0; j < i; j++) {
int diff = nums[i] - nums[j];
Map<Integer, Integer> map = dfs(j);
int cnt = map.getOrDefault(diff, 1) + 1;
memo[i].put(diff, cnt);
ans = Math.max(ans, cnt);
}
return memo[i];
}
}注意有些细节：如果j从i开始倒序遍历到0，则在memo赋值的时候要比较下cnt，因为在等差为0的情况下有可能大的cnt被小的cnt覆盖。
参考资料：