algorithm - 动态编程：带有记忆的递归是否可以与任何递归解决方案或仅特定格式的解决方案一起使用？

Question

我正在阅读有关动态规划的内容，并试图解决最长增加子序列问题。

我试图提出一种蛮力递归方法，在该方法中我生成所有可能的递增子序列并检查哪个是最长的。

private int lis(int[] arr, int k, List<Integer> curr){
    int ans = 0;
    for(int i=k;i<arr.length;i++){
        if(!curr.isEmpty() && arr[i]<=curr.get(curr.size()-1)){
            continue;
        }
        curr.add(arr[i]);
        ans = Math.max(ans, curr.size());
        ans = Math.max(ans,lis(arr,i+1,curr));
        curr.remove(curr.size()-1);
    }
    return ans;
}

这arr是输入数组，k为 0，curr是一个列表，我在其中存储当前递增的子序列，ans是一个全局变量，用于记录最长递增子序列的计数。我得到了这个解决方案的 TLE，这是预期的。

我知道这不是最有效的方法，因为我使用列表来跟踪元素，没有它可以解决问题。但我仍在尝试将此代码应用到记忆中作为练习。

我试图了解记忆化是否可以应用于任何递归蛮力解决方案（或者它是否需要递归解决方案采用特定格式，因为有几种类型的递归，如尾递归等）？如果没有，它应该满足什么属性？

可以将记忆化应用于上述算法以使其工作吗？

标签： algorithmrecursiondynamic-programminglis

Answer 1

只要您能够创建一个查找结构，该结构将识别参数是否相同，就可以执行记忆化，以便您知道何时返回先前的结果。

在 Python 中，atuple就像一个list除了不可变和可散列的，因此它可以在字典中使用。在其他语言中，您通常需要做更多的工作来创建基于元素的查找。那是什么工作取决于语言。最常见的后备方法是创建参数的字符串表示形式。