是否存在一种自顶向下的动态规划解决方案来求解最长递增子序列？

Question

我想知道如何使用自顶向下动态规划查找数组的LIS。是否存在这样的解决方案？能否给我一个使用自顶向下动态规划查找数组LIS的伪代码？我在网上找不到这样的东西，所有的都使用自下而上。

- Some Name

---

下面可以找到Python解决方案。 - Savannah Madison

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)将具有优化的时间复杂度。

- hims92sharma

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]

- Sayakiss

---

这是不正确的，我相信。尝试使用 array = [1, 5, 2, 3, 4, 7, 2]。 - TheRandomGuy

@Dhruv 我的答案还有什么问题吗？请不要犹豫，在这里留下评论问我。 - Sayakiss

Answer 3

我总是尝试以自顶向下和自底向上的相同逻辑进行编写。 我的自底向上方法：

#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;

int n;
vector<int> a, dp;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie();
    cin >> n;
    a.resize(n);
    dp.resize(n);
    for (auto &x : a) {
        cin >> x;
    }

    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], 1 + dp[j]);
            }
        }
    }

    int ans = *max_element(dp.begin(), dp.end());
    cout << ans << '\n';
}

然后我将这个解决方案转换为自顶向下的方式：

#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;

int n;
vector<int> a, dp;

int calc(int i) {
    if (dp[i] != -1) {
        return dp[i];
    }

    dp[i] = 1;
    for (int j = i - 1; j >= 0; j--) {
        if (a[j] < a[i]) {
            dp[i] = max(dp[i], 1 + calc(j));
        }
    }

    return dp[i];
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie();
    cin >> n;
    a.resize(n);
    dp.resize(n, -1);
    for (auto &x : a) {
        cin >> x;
    }

    int ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        ans = max(ans, calc(i));
    } 

    cout << ans << '\n';
}

- Osama Shkukani

---

请阅读此内容：为什么不应该使用#include <bits/stdc++.h>？ 阅读完毕后，请编辑您的答案中的代码，使用标准头文件。 - Adrian Mole

此外，解释你的代码可以帮助其他人理解 :) - nonNumericalFloat

Answer 4

是的，存在一种自顶向下的递归记忆化版本。

数组的每个元素，如果大于前一个元素，则可以选择成为递增子序列的一部分或不是。

如果它不是递增子序列的一部分，我们将忽略该元素并将其不添加到子序列的长度中。

最后，我们需要返回我们所做的两个选择中的最大值。

以下是Python代码。

class Solution:
    def longestSubsequence(self,a,n):
        '''
        Every element, if larger than the prev ele, has a choice, be a part of the increasing subseq or not be
        '''
        memo = {}
        
        def solve(i,prev):
            if i>=n:
                return 0
                
            ky = (i,prev)
            if ky in memo:
                return memo[ky]
                
            ways1 = 0
            if prev==None:
                ways1 = 1+solve(i+1,a[i])
            elif a[i]>prev:
                ways1 = 1 + solve(i+1,a[i])
                
                
            ways2 = solve(i+1,prev)
            
            memo[ky] = max(ways1,ways2)
            return memo[ky]
            
        return solve(0,None)

在这里，字典将作为记忆化数据结构。键是对<indx,prev>的配对，因为两者在每次迭代中都可能会改变。

我们可以使用这个记忆来检索重叠的子问题。

- Savannah Madison

Answer 5

自顶向下方法

#include <iostream>
using namespace std;
int main()
{
    int t;cin>>t;
    while(t--){
    int n; cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];

    int lis[n];
    for(int i=0;i<n;i++) lis[i]=1;
    lis[0]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(arr[i]<arr[j] && lis[i]+1>lis[j])
                lis[j] = lis[i]+1;
        }
    }


    int ans = 1;
    for(int i=0;i<n;i++)
        ans = max(ans,lis[i]);
    cout<<ans<<endl;

    }
    return  0;
}

- asquare14

---

嗯，这是自下而上的方法。OP要求自上而下的方法，也就是递归+记忆化。 - humble