差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:dynamic_programming:longest_common_subsequence [2017/10/08] – ↷ programming:algorithm:dynamic_programming:longest_common_subsequence から programming_algorithm:dynamic_programming:longest_common_subsequence へページを移動しました。 ikatakos | programming_algorithm:dynamic_programming:longest_common_subsequence [2018/05/23] – ikatakos | ||
|---|---|---|---|
| 行 12: | 行 12: | ||
| - | =====最長増加部分列===== | + | =====最長増加部分列の長さ===== |
| 数列の部分列のうち、隣接する2要素を見ると常に右の方が大きいものを増加部分列という。同じ値を許すかは定義によるが、ここでは許さないとする。 | 数列の部分列のうち、隣接する2要素を見ると常に右の方が大きいものを増加部分列という。同じ値を許すかは定義によるが、ここでは許さないとする。 | ||
| 行 30: | 行 30: | ||
| - $A$ の要素を1つずつ順番に処理する。現在処理中の要素を $a_j$ とする。 | - $A$ の要素を1つずつ順番に処理する。現在処理中の要素を $a_j$ とする。 | ||
| - $L[i]$ を、「$a_1$～$a_j$ の要素から長さが $i+1$ の増加部分列を作ったとき、末尾要素が取り得る最小値」とし、更新していく。 | - $L[i]$ を、「$a_1$～$a_j$ の要素から長さが $i+1$ の増加部分列を作ったとき、末尾要素が取り得る最小値」とし、更新していく。 | ||
| - | - 最後まで処理した後の $L$ の長さが、最長増加部分列長となる。 | + | - 最後まで処理した後の $L$ の値が埋まっている所の長さが、最長増加部分列長となる。 |
| <sxh python> | <sxh python> | ||
| 行 52: | 行 52: | ||
| </ | </ | ||
| - | =====最長共通部分列===== | + | =====最長共通部分列の長さ===== |
| * [[http:// | * [[http:// | ||
| 行 69: | 行 69: | ||
| - Bの要素を1つずつ順番に処理する。現在処理中の要素を$b_k$とする。 | - Bの要素を1つずつ順番に処理する。現在処理中の要素を$b_k$とする。 | ||
| - $L[i]$を、「" | - $L[i]$を、「" | ||
| - | - Bを最後まで処理した後の $L$ の長さが、最長増加部分列長となる。 | + | - Bを最後まで処理した後の $L$ の値が埋まっている所の長さが、最長共通部分列長となる。 |
| <sxh python> | <sxh python> | ||
