Longest Increasing Subsequence (LIS) 問題

  Longest Increasing Subsequence (LIS) 問題，並使用二維串列來儲存和計算最長遞增子序列。以下是詳細的程式解釋。

程式邏輯解釋

1. 函式定義與初始化

   def lis(arr):
       n = len(arr)
       dp = [[i] for i in arr]
   

   • arr 是輸入的數列，例如 [1, 3, 8, 5, 6, 7, 4, 9, 2]。
   • n 是數列的長度。
   • dp 是一個二維串列，每個 dp[i] 都初始化為 [arr[i]]，表示只包含當前元素的子序列。這意味著在最壞情況下，每個元素本身就是一個長度為 1 的子序列。

2. 填充 dp 表格

   for i in range(1, n):
       for j in range(0, i):
           if arr[j] < arr[i] and len(dp[j]) + 1 > len(dp[i]):
               dp[i] = dp[j] + [arr[i]]
   

   • 使用雙重迴圈來比較元素：
     • 外層迴圈 i：從 1 到 n-1，遍歷每個元素。
     • 內層迴圈 j：遍歷從 0 到 i-1 的所有元素。
   • 更新邏輯：
     • 如果 arr[j] < arr[i]，表示可以從 j 延伸出一個遞增序列。
     • 並且如果 dp[j] 的長度加 1 大於 dp[i] 的長度，則更新 dp[i] 為 dp[j] + [arr[i]]，表示將 arr[i] 添加到 dp[j] 的序列中，形成更長的 LIS。
     • 這樣做會保證每一個 dp[i] 都儲存從開頭到 i 位置的最長遞增子序列。

3. 找出最長的 LIS

   longest_lis = max(dp, key=len)
   return longest_lis, len(longest_lis)
   

   • 使用 max(dp, key=len) 來找出 dp 中長度最長的子序列。
   • 返回最長的遞增子序列及其長度。

4. 測試程式碼

   arr = [1, 3, 8, 5, 6, 7, 4, 9, 2] 
   str1, len1 = lis(arr)
   print(str1, len1)
   

   • 給定數列 arr = [1, 3, 8, 5, 6, 7, 4, 9, 2]，調用 lis 函式。
   • 打印最長遞增子序列及其長度。

執行結果：

[1, 3, 5, 6, 7, 9] 6

解釋：

1. 初始化：dp 初始為 [[1], [3], [8], [5], [6], [7], [4], [9], [2]]。
2. 逐步更新 dp：
   • 當 i = 2 (arr[2] = 8) 時，j = 1 (arr[1] = 3) 使得 dp[2] 更新為 [1, 3, 8]。
   • 當 i = 3 (arr[3] = 5) 時，j = 1 (arr[1] = 3) 使得 dp[3] 更新為 [1, 3, 5]。
   • 當 i = 5 (arr[5] = 7) 時，j = 4 (arr[4] = 6) 使得 dp[5] 更新為 [1, 3, 5, 6, 7]。
   • 最後，當 i = 7 (arr[7] = 9) 時，j = 5 (arr[5] = 7) 使得 dp[7] 更新為 [1, 3, 5, 6, 7, 9]。
3. 找出最長 LIS：在 dp 中長度最長的子序列是 [1, 3, 5, 6, 7, 9]，長度為 6。

總結：

• 使用二維 dp：每個 dp[i] 保存從開頭到 i 位置的最長遞增子序列。
• 更新邏輯：透過比較前面所有的元素，動態更新 dp[i] 來找到新的 LIS。
• 時間複雜度：O(n²) 由於雙重迴圈的存在。
• 優點：可以直接得到實際的 LIS，而不需要另外反向追踪。