Register | Login

Solutions of Longest common subsequence

Select solution language All Tiếng Việt English Other

Write solution here.

---

ijk    Created at    6 likes

Tư tưởng giống với bài LCS của xâu. Gọi $dp[i][j]$ là độ dài dãy con chung của 2 mảng lớn nhất khi xét đến $i$ số đầu tiên của A và $j$ số đầu tiên của B Nếu $a_i == b_j$: $dp[i][j]=dp[i-1][j-1]+1$ (2 số giống nhau thì lấy đáp án của $i - 1$ số trước của A và $j-1$ số trước của B để nối thêm) Ngược lại: $dp[i][j]=max(dp[i-1][j], dp[i][j-1])$ (ta sẽ lấy kết quả $i-1$ số trước hoặc $j-1$ số trước và lấy max) Kết quả bài toán là $dp[n][n]$