動的計画法による部分列問題の徹底攻略：1次元・2次元、連続・非連続の各パターン
1. 不相交の線 (LeetCode 1035)
この問題は、一見すると幾何学的な制約があるように見えますが、本質的には「最長共通部分列 (LCS)」を求める問題と同じです。2つの配列間で線を引く際に交差させないという条件は、選ぶ要素の相対的な順序を維持することを意味します。
アルゴリズムの定義
dp[i][j] を、配列 data1 の最初の i 個の要素と、配列 data2 の最初の j 個の要 ...
7月7日 17:15 投稿