3

動的計画法を使用して最長増加サブシーケンスの長さを調べるために、この実装を作成しました。[10, 22, 9, 33, 21, 50, 41, 60, 80] の入力の場合、LIS は 6 で、セットの 1 つは [10, 22, 33, 50, 60, 80] です。

以下のコードを実行すると、O(n) の複雑さで 6 という正しい答えが得られます。それが正しいか？

def lis(a):
    dp_lis     = []
    curr_index = 0
    prev_index = 0

    for i in range(len(a)):
        prev_index = curr_index
        curr_index = i

        print 'if: %d < %d and %d < %d' % (prev_index, curr_index, a[prev_index], a[curr_index])
        if prev_index < curr_index and a[prev_index] < a[curr_index]:
            print '\tadd ELEMENT: ', a[curr_index]
            new_lis = 1 + max(dp_lis)
            dp_lis.append(new_lis)
        else:
            print '\telse ELEMENT: ', a[curr_index]
            dp_lis.append(1)

    print "DP LIST: ", dp_lis
    return max(dp_lis)

if __name__ == '__main__':
    a = [10, 22, 9, 33, 21, 50, 41, 60, 80]
    print lis(a)
4

2 に答える 2

1

私は動的計画法アルゴリズムをかなり頻繁に実装しています。

正確性をチェックする最善の方法は、アルゴリズムのブルート フォース バージョンを記述し、その出力を小さな例での動的プログラミングの実装と比較することであることがわかりました。

2 つのバージョンの出力が一致する場合、妥当な正確さの自信があります。

于 2013-04-20T15:54:22.500 に答える