我想知道如何使用自顶向下动态规划查找数组的LIS。是否存在这样的解决方案?能否给我一个使用自顶向下动态规划查找数组LIS的伪代码?我在网上找不到这样的东西,所有的都使用自下而上。
我想知道如何使用自顶向下动态规划查找数组的LIS。是否存在这样的解决方案?能否给我一个使用自顶向下动态规划查找数组LIS的伪代码?我在网上找不到这样的东西,所有的都使用自下而上。
使用递归方法解决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)将具有优化的时间复杂度。
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]
array = [1, 5, 2, 3, 4, 7, 2]
。 - TheRandomGuy我总是尝试以自顶向下和自底向上的相同逻辑进行编写。 我的自底向上方法:
#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';
}
是的,存在一种自顶向下的递归记忆化版本。
数组的每个元素,如果大于前一个元素,则可以选择成为递增子序列的一部分或不是。
如果它不是递增子序列的一部分,我们将忽略该元素并将其不添加到子序列的长度中。
最后,我们需要返回我们所做的两个选择中的最大值。
以下是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>的配对,因为两者在每次迭代中都可能会改变。
我们可以使用这个记忆来检索重叠的子问题。
自顶向下方法
#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;
}