关于740号问题，写了回溯的算法，不太清楚这道题如何定义memo?
来源：11-2 更多经典面试问题
Llizzzc
2024-04-11
import java.util.ArrayList;
class Solution {
private boolean[] visited;
public int deleteAndEarn(int[] nums) {
visited = new boolean[nums.length];
int res = 0;
for (int i = 0; i < nums.length; i ++) {
res = Math.max(delete(nums, i), res);
}
return res;
}
// 获取删除e之后的最大价值
public int delete(int[] nums, int index) {
visited[index] = true;
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < nums.length; i ++) {
if (!visited[i] &&
(nums[i] == nums[index] + 1 || nums[i] == nums[index] - 1)) {
visited[i] = true;
list.add(i);
}
}
int res = 0;
for (int i = 0; i < nums.length; i ++) {
if (!visited[i]) {
res = Math.max(res, delete(nums, i));
}
}
visited[index] = false;
for (int i : list) {
if (visited[i] &&
(nums[i] == nums[index] + 1 || nums[i] == nums[index] - 1)) {
visited[i] = false;
}
}
return res + nums[index];
}
}
写回答
1回答
-
liuyubobobo
2024-04-18
你写的回溯算法是无法通过添加 memo 改成动态规划的。因为你的回溯算法的状态是有后效性的。即后续的状态和之前的状态是相关的。因为在每次操作 delete(nums, index) 的时候，下一次能删除哪个元素，和之前删除过哪个元素息息相关。
请仔细体会一下，你的这个问题确实是动态规划的难点，也是重点。对于动态规划来说，怎么定义状态至关重要。不是能写出回溯算法就能改成动态规划的。
这个问题可以怎么定义状态，请理解一下我的参考代码和对应的状态定义方式（由于我手头的系统写 C++ 方便，所以以下是 C++ 代码，你可以在理解的基础上，改成 Java 代码）：
class Solution { public: int deleteAndEarn(vector<int>& nums) { // 对 nums 的排序不影响最终结果。 // 这里为什么要对 nums 排序？请将其作为一个思考题，在理解了下面的算法后，回过头回答这个问题。 sort(nums.begin(), nums.end()); vector<int> memo(nums.size(), -1); return dfs(nums, 0, memo); } private: // dfs(nums, index) 的定义是，下面在 nums[index...nums.size()) 的范围里删除元素， // 可以得到的最大分值是多少 int dfs(const vector<int>& nums, int index, vector<int>& memo){ // 如果 index >= nums.size()，一个元素都删不了，分值为 0 if(index >= nums.size()) return 0; // 记忆化搜索。如果 memo[index] 不为 -1， // 则之前计算过 nums[index...nums.size()) 的范围里删除元素可以得到的最大分值 // 直接返回 if(memo[index] != -1) return memo[index]; // 索引 i1 指向比 nums[index] 大的下一个元素的索引 // 如果 nums[index...nums.size()) 为 2, 2, 2, 3, 3, 5, 6 // 则 i1 指向第一个 3 的索引 int i1; for(i1 = index; i1 < nums.size() && nums[i1] == nums[index]; i1 ++); // 索引 i2 指向比 nums[index] + 1 大的下一个元素的索引 // 如果 nums[index...nums.size()) 为 2, 2, 2, 3, 3, 5, 6 // 则 i2 指向第一个 5 的索引 // 如果 nums[index...nums.size()) 为 2, 2, 2, 4, 4, 5, 6 // 则 i2 指向第一个 4 的索引，此时 i2 和 i1 一致 int i2; for(i2 = i1; i2 < nums.size() && nums[i2] == nums[index] + 1; i2 ++); // 面对当前 在 nums[index...nums.size()) 的范围里删除元素，有两个选择 // 选择 1，选择删除 nums[index] 以及所有和 nums[index] 相同的元素。 // 整个数组中一共有 (i1 - index) 个 nums[index] 这么大的元素，分值加上 nums[index] * (i1 - index) // 之后，数组中 nums[i1...i2) 这个范围里的元素不能选了，因为他们比 nums[index] 大一 // 之后，只要计算在 nums[i2...nums.size()) 的范围里删除元素可以得到的最大分值即可 int res1 = nums[index] * (i1 - index) + dfs(nums, i2, memo); // 选择 2，不选择删除 nums[index] // 之后，只要计算在 nums[i1...nums.size()) 的范围里删除元素可以得到的最大分值即可 int res2 = dfs(nums, i1, memo); return memo[index] = max(res1, res2); } };请仔细理解在上述逻辑的状态定义中，这个状态是无后效性的。也就是当我面对在 nums[index....nums.size()) 这个子数组中删除元素，找最大分值的时候，是和在 nums[0...index) 这个区间里怎么删除元素，完全无关的。
继续加油！：）
032024-04-29
相似问题