6

计算数组中的 LIS（最长递增子序列）是一个非常著名的动态规划问题。然而，在每个教程中，他们首先在不使用 DP 概念的情况下展示递归解决方案，然后通过应用自底向上 DP（迭代解决方案）来解决它。

我的问题是：

我们将如何在 递归解决方案本身中使用记忆化。不只是记忆化，而是使用一维数组记忆化。

我做了一些研究，但找不到任何相关的东西。虽然有 2 个地方要求递归记忆1和 2，但那里的解决方案是使用 2D Map / Array 进行记忆。

无论如何，用一维数组记忆解决方案会给出错误的输出。这是我所做的：

int lis(int idx, int prev)
{
    if(idx >= N)
        return 0;

    if(dp[idx])
        return dp[idx];

    int best_ans = lis(idx+1, prev);

    int cur_ans = 0;
    if(arr[idx] > prev)
    {
        cur_ans = 1 + lis(idx+1, arr[idx]);
    }
    int ans = max(best_ans, cur_ans);
    dp[idx] = ans;
    return ans;
}

int main()
{
    // Scan N 
    // Scan arr

    ans = lis(0, -1));
    print ans;
}

虽然我知道这个解决方案给出错误输出的原因是：

根据先前的值，给定索引可以有多个解决方案。

但我仍然想知道如何使用一维数组来完成。

我很想知道解决方案，因为我已经读过每个 DP自上而下的解决方案都可以重新构建为自下而上的解决方案，反之亦然。

如果有人可以提供一些见解，那将非常有帮助。

提前致谢。

4

3 回答 3

5

这是无法做到的，因为这个问题从根本上需要一个二维数据结构来解决。

自下而上的方法可以通过在数据结构中一次生成一行来作弊。随着时间的推移，它会产生一个二维数据结构，但在任何给定时间你只能看到它的一个维度。

自上而下的方法必须构建整个二维数据结构。

这是 DP 的基本权衡。写下自上而下的方法通常更容易。但自下而上的方法在任何时候都只需要拥有整体数据结构的一部分，因此内存需求显着降低。

于 2017-02-20T18:53:52.977 回答
1 
def LongestIncreasingSubsequenceMemo(nums, i, cache):
    if cache[i] > 0:
        return cache[i]
    result = 1
    for j in range(i):
        if nums[i] > nums[j]:
            result = max(result, 1 + LongestIncreasingSubsequenceMemo(nums, j, cache))
    cache[i] = result
    return result

def main():
    nums = [1,2,3,4,5]
    if not nums:
        return 0        
    n = len(nums)
    cache = [0 for i in range(n)]
    result = 1
    for i in range(n):
        result = max(result, LongestIncreasingSubsequenceMemo(nums, i, cache))
    return result

if __name__ == "__main__":
    print(main())

在上述解决方案中，我们采用一维数组并为数组中的每个元素更新它。

于 2019-08-28T16:24:03.393 回答
0

这可以做到，并且不需要二维数组。因为我们需要找到在每个索引处结束的最大 LIS 所以如果我们为 arr[0] 处的元素计算 LIS，而不是一次又一次地计算，我们计算一次并将其存储在 DP[1] 中。

如果我们为 {arr[0],arr[1]} 计算 LIS，那么我们将结果存储在 DP[2] 中，依此类推，直到 DP[n]。请参阅下面的代码以完全理解这一点。

递归代码的记忆

上面的代码也被 gfg 接受了

于 2021-08-29T17:25:22.463 回答