Longest Common Sub-sequence Problem(最長公共子序列) Back

Overview

  • 求出最短裝配時間
  • 主程序的時間複雜度:
  • 追溯最優解的時間複雜度:
  • : S1序列取前i個, S2序列取前j個時的最長公共子序列長度值. (用於求最優解的值)
  • : S1序列取前i個, S2序列取前j個時, 是如何求得. (用於求最優解)

Optimal Substructure

  • 當我們知道若求的時候, 若S1序列的最後一個字符與S2的最後一個字符相同, 則該字符一定在公共子序列中, 因此的值必定是的值加一; 否則, 的值將是中較大的一個.

Recursive Expression

Solution

  • 最優解: 通過反向遍曆, 找到最優解.
  • 最優解的值:

results matching ""

    No results matching ""