Pythonで解く【初中級者が解くべき過去問精選 100 問】(053 - 055 動的計画法：その他) - Qiita

1. 目的 初中級者が解くべき過去問精選 100 問をPythonで解きます。 すべて解き終わるころに水色になっていることが目標です。 本記事は「053 - 055 動的計画法：その他」です。 2. 総括 「その他」とあるようにこの3問は今までのdpとは少し志向（嗜好？）が違い、dpらしくないdpであると感じました。 3. 本編 053 - 055 動的計画法：その他 053. DPL_1_D - 最長増加部分列 回答 import bisect n = int(input()) A = [int(input()) for _ in range(n)] dp = [A[0]] for i in range(1, n): if A[i] > dp[-1]: dp.append(A[i]) else: ind = bisect.bisect_left(dp, A[i]) dp[ind] = A