是否存在最长递增子序列的自上而下动态规划解决方案？

Question

我想知道如何使用自上而下动态规划找到数组的 LIS。是否存在一种这样的解决方案？你能给我提供使用自顶向下动态规划查找数组 LIS 的伪代码吗？我无法在互联网上找到一个。他们都使用自下而上。

Answer 1

在java中解决LIS长度的递归方法如下 -

 public int LIS(int[] arr) {
        return LISLength(arr, Integer.MIN_VALUE, 0);
    }

    public int LISLength(int[] arr, int prev, int current) {
        if (current == arr.length) {
            return 0;
        }
        int include = 0;
        if (arr[current] > prev) {
            include = 1 + LISLength(arr, arr[current], current + 1);
        }
        int exclude = LISLength(arr, prev, current + 1);
        return Math.max(include, exclude);
    }

但它可以使用 O(2^n) 时间复杂度，所以我们需要使用记忆技术来降低复杂度，下面的方法 -

public int LIS(int[] arr) {
        int memoTable[][] = new int[arr.length + 1][arr.length];
        for (int[] l : memoTable) {
            Arrays.fill(l, -1);
        }
        return LISLength(arr, -1, 0, memoTable);
    }
    public int LISLength(int[] arr, int prev, int current, int[][] memoTable) {
        if (current == arr.length) {
            return 0;
        }
        if (memoTable[prev + 1][current] >= 0) {
            return memoTable[prev + 1][current];
        }
        int include = 0;
        if (prev < 0 || arr[current] > arr[prev]) {
            include = 1 + LISLength(arr, current, current + 1, memoTable);
        }

        int exclude = LISLength(arr, prev, current + 1, memoTable);
        memoTable[prev + 1][current] = Math.max(include, exclude);
        return memoTable[prev + 1][current];
    }

所以 O(n^2) 将通过记忆技术优化时间复杂度。

Answer 2

当然。定义：

F(n) = 序列 1..n 的最长递增子序列，并且该序列必须以元素_n结尾

然后我们得到递归函数（自上而下）：

F(n) = max(len(F(i)) + 1) 其中 0 <= i < n 且 array[i] < array[n]

所以答案是：

F(1..n) 的最长递增子序列

通过记忆化，我们得到了这段代码（这是Python，它比伪代码更好）：

    d = {}
    array = [1, 5, 2, 3, 4, 7, 2]
    
    def lis(n):
        if d.get(n) is not None:
            return d[n]
        length = 1
        ret = [array[n]]
        for i in range(n):
            if array[n] > array[i] and len(lis(i)) + 1 > length:
                length = len(lis(i)) + 1
                ret = lis(i) + [array[n]]
        d[n] = ret
        return ret
    
    def get_ans():
        max_length = 0
        ans = []
        for i in range(len(array)):
            if max_length < len(lis(i)):
                ans = lis(i)
                max_length = len(lis(i))
        return ans
    
    print get_ans() # [1, 2, 3, 4, 7]