动态规划练习1 http://www.hawstein.com/posts/dp-novice-to-advanced.html

dp_1.py

# http://www.hawstein.com/posts/dp-novice-to-advanced.html
# d(i) = max{1, d(j)+1}, 其中j<i, A[j]<=A[i]

def longest_increasing_sequence(A):
    n = len(A)
    d = [0] * n
    last_idx_to_this_one = [0] * n
    length = 1

    for i in range(0, n):
        d[i] = 1
        last_idx_to_this_one[i] = i
        for j in range(0, i):
            if (A[j] <= A[i]) and (d[j] + 1 > d[i]):
                d[i] = d[j] + 1
                last_idx_to_this_one[i] = j
        if d[i] > length:
            length = d[i]

    return (d, last_idx_to_this_one, length)

def find_lis(A, d, last_indices):
    start_pos = d.index(sorted(d)[-1])
    longest_subsequence = []

    def find(A, last_indices, start_pos, lis):
        num = A[start_pos]
        lis.insert(0, num)

        new_pos = last_indices[start_pos]

        if new_pos != start_pos:
            find(A, last_indices, new_pos, lis)
        else:
            return lis

    find(A, last_indices, start_pos, longest_subsequence)
    return longest_subsequence

if __name__ == '__main__':
    A = [5, 3, 4, 8, 6, 7]
    (d, last_indices, length) = longest_increasing_sequence(A)
    print(A)
    print(d)
    print(last_indices)
    print(length)
    print(find_lis(A, d, last_indices))

Unbelievable.....The Code is not as simple as C++.

... i mean it doesn't have pythons ...succinct ? ...emm ...pithy! yes is so prolix. can you take a new one?