给定条件的最长子序列

Question

我认为这个问题可以用动态规划来解决，但我不能提出递归关系。

Answer 1

假设您正在处理数组A，选择要包含在子序列中的值。在每个步骤中，您可以(a)包括当前值，或者(b)不包括它。如果您记住了这两个选项中较好的一个，那么应该可以使动态编程工作。

在伪代码中,函数应该如下所示：

int longest_subseq(ix, available_weight, last_val):
    # Parameters:
    # ix = an index into array A (assumed to have global scope)
    # available_weight = the remaining weight avaiable for the subsequence
    #                    starting at ix
    # last_val = the last value in the subsequence from A[0] through A[ix-1]

    # When first called, create a DP array of 10^5 × 51 × 51 elements
    # (This will use about 1GB of memory, which I assume is OK)
    if DP is undefined:
        DP = new array(100001, 51, 51)
        initialize every element of DP to -1

    # Return memoized value if available
    v = DP[ix, available_weight, last_val]
    if v >= 0:
        return v

    # Check for end conditions
    if ix == n or available_weight == 0:
        return 0

    # Otherwise you have two options; either include A[ix] in the
    # subsequence, or don't include it
    len0 = longest_subseq(ix+1, available_weight, last_val)
    if abs(A[ix] - last_val) > available_weight:
        DP[ix, available_weight, last_val] = len0
        return len0
    len1 = 1 + longest_subseq(ix+1, available_weight-abs(A[ix]-last_val), A[ix])
    if len0 > len(1):
        DP[ix, available_weight, last_val] = len0
        return len0
    else:
        DP[ix, available_weight, last_val] = len1
        return len1

如果然后调用longest_subseq(0,k,a[0])，则函数应在合理的时间内返回正确的答案。