关于740号问题，写了回溯的算法，不太清楚这道题如何定义memo?

Question

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];
    } 
}

Answer 1

liuyubobobo 2024-04-18 10:37:32

你写的回溯算法是无法通过添加 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) 这个区间里怎么删除元素，完全无关的。

继续加油！：）

• 提问者 Llizzzc #1

  首先，非常感激bobo老师的耐心解答！！
  
  一：关于状态的后效性，老师所说的“后续的状态和之前的状态是相关的”，关于“之前的状态”我没能很好理解。例如，在老师的定义中，nums[index....nums.size()) 代表后续状态，而nums[0...index) 是之前的状态，是这样理解的吗？但是，在动态规划的转移中，nums[index....nums.size()) 是由nums[index2....nums.size()) ，index2 >index转移而来的，这个nums[index2....nums.size())的状态我的理解也是代表“之前”的状态，因此关于这个“之前的状态”有点弄不清楚。
  
  二：关于老师说的“不是能写出回溯算法就能改成动态规划的”。看完老师的解答之后，如果说是“正确”定义好了回溯算法，即“状态的定义”，是不是就能通过记忆化的方式来解决问题，这个命题是正确的吗？因为我看leetcode的官方题解是通过将问题转化成打家劫舍进行解决的，关于这类“技巧性”的问题其实都是可以通过回溯解决的，在正确定义好了回溯算法的前提下，可以这样理解吗？
  
  三：关于选择使用dp和记忆化的倾向性，老师认为应该将精力更放在哪种解决方式上？

• liuyubobobo 回复 提问者 Llizzzc #2

  1. 
  
  我的递归函数是 dfs(const vector<int>& nums, int index, vector<int>& memo)，其中的 nums 是不变的，memo 是做辅助记忆的，所以整个函数的状态只和 index 有关，简写成 dfs(index)，其定义就是“在 nums[index...nums.size()) 的范围里删除元素，可以得到的最大分值是多少。”
  
  在 dfs(index) 里，会调用 dfs(i1) 和 dfs(i2)。dfs(i1) 和 dfs(i2) 就是 dfs(index) 的后续状态。为了求解出 dfs(index)，必须求解出 dfs(i1) 和 dfs(i2)。（具体的，因为 i1 和 i2 一定大于 index，可以理解成为了求出 dfs(x)，必须先求出所有 y > x 的情况下的 dfs(y)）
  
  无后效性的意思就是，dfs(i1) 和 dfs(i2) 是多少，和 dfs(index) 无关。
  
  而对于你的算法，也是 dfs(index)，但定义是从当前数组中删除掉 index 位置的元素，可以得到的最大值是多少。但是这个值，是和之前删除掉谁相关的。也就是不具备无后效行。
  
  2.
  
  “正确”定义好了回溯算法，即“状态的定义”，是不是就能通过记忆化的方式来解决问题？
  
  是的。或者更准确的说，正确定义好了状态，就能用动态规划了。但是，不是所有的问题都能有“正确的状态定义”的。因为不是所有的问题，都能找到“无后效性”的状态的。
  
  “关于这类“技巧性”的问题其实都是可以通过回溯解决的，在正确定义好了回溯算法的前提下，可以这样理解吗？”抱歉，这句话我没有看懂。
  
  3. 关于选择使用dp和记忆化的倾向性，老师认为应该将精力更放在哪种解决方式上？
  
  在正常情况下，通过训练，你应该会觉得使用记忆化搜索比 dp 简单。所以我个人的建议是去使用记忆化搜索解决近乎所有的 dp 问题。然后如果觉得有必要，可以再把代码改写成 dp 代码。（有一些时候其实并没有这个必要。）
  
  熟练到一定程度（这个过程训练到一定程度），对于比较明显的问题，慢慢应该能够直接写 dp 代码了。对于大多数人，应该是这样的顺序。
  
  比如对于这个问题，我给出的记忆化搜索代码，是可以改写成 dp 代码的，试试看？
  
  继续加油！：）

• 提问者 Llizzzc 回复 liuyubobobo #3

  回复 liuyubobobo：再次感谢老师的耐心解答！！！