Số lượng gia tăng các chiều dài k

Question

Tôi đang cố gắng hiểu thuật toán cung cấp cho tôi số lượng gia tăng độ dài K trong một mảng trong thời gian O (n k log (n)). Tôi biết làm thế nào để giải quyết vấn đề này rất giống nhau bằng cách sử dụng thuật toán O (k * n^2). Tôi đã tra cứu và phát hiện ra giải pháp này sử dụng BIT (Fenwick Tree) và DP. Tôi cũng đã tìm thấy một số mã, nhưng tôi đã không thể hiểu được nó.

Dưới đây là một số liên kết tôi đã truy cập đã hữu ích.

Here in SO
Topcoder forum
Random webpage

Tôi thực sự sẽ đánh giá cao nếu một số có thể giúp tôi ra hiểu thuật toán này.

Answer 1

Tôi tái tạo thuật toán của tôi từ here, nơi logic của nó được giải thích:

dp[i, j] = same as before num[i] = how many subsequences that end with i (element, not index this time) 
     have a certain length 

for i = 1 to n do dp[i, 1] = 1 

for p = 2 to k do // for each length this time num = {0} 

    for i = 2 to n do 
    // note: dp[1, p > 1] = 0 

    // how many that end with the previous element 
    // have length p - 1 
    num[ array[i - 1] ] += dp[i - 1, p - 1] *1* 

    // append the current element to all those smaller than it 
    // that end an increasing subsequence of length p - 1, 
    // creating an increasing subsequence of length p 
    for j = 1 to array[i] - 1 do *2*  
     dp[i, p] += num[j] 

Bạn có thể tối ưu hóa *1* và *2* bằng cách sử dụng cây phân khúc hoặc cây được lập chỉ mục nhị phân. Những điều này sẽ được sử dụng để xử lý một cách hiệu quả các hoạt động sau đây trên mảng num:

• Với (x, v) thêm v để num[x] (thích hợp cho *1*);
• Cho x, tìm số tiền num[1] + num[2] + ... + num[x] (có liên quan đến *2*).

Đây là những vấn đề tầm thường cho cả hai cấu trúc dữ liệu.

Lưu ý: Điều này sẽ có độ phức tạp O(n*k*log S), trong đó S là giới hạn trên trên các giá trị trong mảng của bạn. Điều này có thể hoặc có thể không đủ tốt. Để làm cho nó O(n*k*log n), bạn cần phải bình thường hóa các giá trị của mảng của bạn trước khi chạy thuật toán trên. Bình thường hóa có nghĩa là chuyển đổi tất cả các giá trị mảng của bạn thành các giá trị nhỏ hơn hoặc bằng n. Vì vậy, đây:

5235 223 1000 40 40 

trở thành:

4 2 3 1 1 

Điều này có thể được thực hiện với một loại (giữ các chỉ số ban đầu).