递归关系和重叠子问题

Question

我是动态规划的新手，我正在尝试了解递归和记忆的基础知识，同时尝试解决非相邻元素的最大和 - Problem。在阅读了一些理论之后，递归函数的基本属性之一是它应该具有重叠子问题。对于这个问题的天真蛮力方法，对于我下面的代码，我很难看到重叠的问题。

我看不到重叠子问题的原因是因为我没有递归关系吗？
我是否总是必须有递归关系才能有子问题，即所有递归问题may/may如果没有递归关系就没有子问题
如果 1 或 2 成立并且我只是在分析时出错，我该如何添加记忆？

public static int maxSubsetSum(int[] arr) {
        HashMap<Integer, Integer> cache = new HashMap<Integer, Integer>();
        return maxSumHelper(arr, 0, arr.length , 0, new ArrayList<Integer>(), cache);
    }
    public static int maxSumHelper(int[]arr, int start, int end, int sum, ArrayList<Integer>combo, HashMap<Integer, Integer> cache){
        
        /*
         * if(cache.containsKey(start)) { return; }
         */
        if(start>=end){
            for(int i  = 0; i <combo.size();i++ ) {
                System.out.print(combo.get(i));
            }
            System.out.println();
            return sum;
        }
        for(int i = start; i < arr.length; i++){
            sum+= arr[i];
            combo.add(arr[i]);
            int withMax  = maxSumHelper(arr, i + 2, end, sum, combo, cache);
            sum-=arr[i];
            combo.remove(combo.size() - 1);
            int withoutMax = maxSumHelper(arr, i+ 2, end, sum, combo, cache);
            //cache.put(i, Math.max(withMax, withoutMax));
            max = Math.max(max,Math.max(withMax, withoutMax));
        }
        return max;
    }

Answer 1

one of the basic properties of a recursive function is it should have over lapping sub problems

这是从动态规划中获益的条件，但通常不是递归函数的条件。

I am having a hard time seeing overlapping problems.

他们在那里。但首先更正：第二个递归调用应该传递 i+1 作为参数，而不是 i+2。这是因为它处理的情况是您不将 i 的值包括在总和中，因此允许包括 i+1 的值.

现在采用这个示例输入，并寻找最大化的总和：

{ 1, 2, 3, 2, 0, 3, 2, 1 }
                 ^
                 i=5

让我们关注作为参数的调用 start=5：我们最多可以 add 到当前总和是 3 + 1 = 4。这个事实是独立的关于 sum 参数的值是什么，因此我们可以从缓存中受益，它会告诉我们给定索引 [=17= 处的最大化附加值是多少].

有许多路径通向 start=5 的调用。路径 (combo) 可以包含输入 before 索引 5:

中的任何这些值

1、3、0
1, 2
2, 2
2, 0
3, 0
2
0
无

所以如果第一种情况下钻到最后，确定索引5的最大附加值是4（3+1），那么其他情况就不需要再做这个搜索了，就可以了就做 return sum + cache.get(start).

旁注

更好的做法是让递归函数 return 那个“附加”总和，并且不将总和作为参数传递给它。只需将当前选择的值（如果有的话）添加到从递归调用和 return that 返回的总和中的最大值。这样也更清楚如何使用记忆。

递归关系和重叠子问题

Recursion relation and overlapping sub problems

algorithm

recursion

dynamic-programming

旁注