Hỏi về cách đếm LIS

#1

Em đang mắc kẹt ở bài Number of Longest Increasing Subsequence - LeetCode và đang tham khảo cách giải thích ở trang Longest increasing subsequence - Algorithms for Competitive Programming (cp-algorithms.com)

Phần giải thích:

The number of ways to form a longest increasing subsequences ending in a[i] is the sum of all ways for all longest increasing subsequences ending in j where d[j] is maximal. There can be multiple such j , so we need to sum all of them.

Em đã hoàn thành bài Longest Increasing Subsequence - LeetCode dùng segment tree nhưng đến bài trên thì bí không hiểu lắm cách giải thích ở trên. Mọi người giải thích rõ ràng nhất cách giải thích ở trên giúp em với ạ! :sweat_smile: :sweat_smile:

Cách hiểu của em: Với mỗi a_i, ta xét các index j < i sao cho tại đó có thể thành lập được LIS(d[j] = max_len, d là mảng các độ dài của local-LIS thành lập tại j trong A). Tổng số cách thành lập LIS ở các vi trí này sao mà bằng số cách thành lập LIS kết thúc bằng a_i được ạ?

#2

Ví dụ:
a = [5 6 7 8 -4 -3 -2 -1 9]
QHĐ:
d = [1 2 3 4 1 2 3 4 ?]

Bây giờ cần một mảng QHĐ nữa là số LIS kết thúc tại i count[i], tức là nếu d[j] đúng bằng số lớn nhất thì cộng count[j] vào count[i], còn lớn hơn thì khởi tạo count[i] = count[j].

Ở đây LIS[4] = LIS[8] = max nên count[9] = count[4] + count[8].
count = [1 1 1 1 1 1 1 1 2]

1 Like
#3

Cảm ơn anh đã trả lời post ạ :D. Ý em là thắc mắc tại sao lại cộng như vậy ý ạ. Còn về ví dụ của anh hình như nó sai thì phải vì: các LIS kết thúc tại 9(chỉ số) là 5 6 7 9, 6 7 8 9, -4 -3 -2 9, -3 -2 -1 9. Sao count[9] lại là 2 ạ?

Tổng số cách thành lập LIS ở các vi trí này sao mà bằng số cách thành lập LIS kết thúc bằng a_i được ạ?

#4

Không phải, chỉ có 2 LIS kết thúc tại chỉ số 9 là (5 6 7 8 9) và (-4 -3 -2 -1 9).

Trở lại với hệ thức truy hồi cho d: Với d_i là độ dài LIS kết thúc tại i thì d_i = \max(1, \underset{\substack{1 \leq j < i\\a_j < a_i}}{\max}(1+d_j)) tức là j chạy từ 1 đến i - 1. Khi điều kiện a_j < a_i được thỏa mãn, dãy LIS kết thúc tại j có thể bổ sung a_i nên cộng thêm 1.

Còn vì sao count[i] cộng thêm count[j] (khi d[j] đang bằng max) là do quy tắc cộng tổ hợp :smiley: Dãy LIS kết thúc tại i = (LIS kết thúc tại j), a[i]; mà mỗi LIS i chỉ chọn 1 LIS j thôi, nên cộng lại tất cả các count[j] với j để a[j] và d[j] thỏa mãn điều kiện. Quy tắc cộng phát biểu như sau: Nếu

  • trường hợp A có a cách thực hiện
  • trường hợp B có b cách thực hiện
    …

mà A, B, … đôi một không trùng lặp thì số cách là a + b + …

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?