0

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

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

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，这是预期的。

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

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

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

4

1 回答 1

1

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

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

于 2021-03-05T21:24:11.300 回答