經典動態規劃問題:最長公共/遞增子序列

2021-02-21 花花醬LeetCode

哈嘍，大家好！我是花花。今天我們一起來看一下兩個僅有一"字"之差的經典的動態規劃問題：

最後我們會以一道LeetCode題目為例子，看看如何在特定情況下把LCS歸約成LIS從而降低時間複雜度。

在講具體問題之前我們先來舉個例子看一下什麼是子序列（subsequence）以及它和子數組（subarray）和子集（subset）之間的區別。

假設我們有一個數組：[1, 2, 3, 4, 5]。

[1,2,3]是一個子序列，同時也是一個子數組。

[1,3,5]是一個子序列，但卻不是一個子數組，因為子數組要求元素連續。

[3,1,5]是一個子集，但既不是一個子序列，也不是一個子數組。因為後兩者都要元素順序不能改變。

給定兩個數組A和B，找出兩者共同擁有的子序列中長度最長的一個。通常只需要返回長度即可。

A: [6,4,8,1,3,2]

B: [4,7,6,2,3,8,6,1]

LCS(A, B) = [4,8,1]（[6,8,1]也是一個解）

我們可以這樣來定義dp數組：

dp[i][j] := LCS(A[0~i], B[0~j])

當A[i] == B[j]時，子序列的長度增加1。

dp[i][j] = dp[i-1][j-1] + 1

如果A[i] != B[j]，跳過當前匹配，在dp[i][j-1]和dp[i-1][j]中取一個最大值。

合在一起的話我們可以得到下面的轉移方程：

dp數組初始化成0

假設len(A) = m, len(B) = n

答案就存儲在dp[m][n]中（加了padding）

空間複雜度O(mn)

時間複雜度O(mn)

參考代碼：

# Author: Huahua        class Solution:  def LCS(self, A: List[int], B: List[int]) -> int:    m, n = len(A), len(B)    dp = [[0] * (n + 1) for _ in range(m + 1)]    for i in range(1, m+1):      for j in range(1, n+1):        dp[i][j] = max((dp[i-1][j],                        dp[i][j-1],                        dp[i-1][j-1] + int(A[i-1] == B[j-1])))    return dp[m][n]
和最長公共子序列不同，最長遞增子序列的輸入只有一個數組。要求返回該數組最長的一個子序列並且子序列中所有的元素嚴格單調遞增。
A: [1,4,2,3,6,5,9,4]
LIS(A) = [1,2,3,5,9] 長度是5，如下圖所示：
由於輸入只有一個數組，所以我們的dp數組也變成了一維：
dp[i] := 以A[i]結尾的LIS的長度
轉移方程比較簡單：
dp[i] = max(dp[j]) + 1, 0 <= j < i and A[i] > A[j]
如果A[i] > A[j]，那麼A[i]就可以接在A[j]後面擴展以A[j]結尾的最長遞增子序列。所以對於i，我們枚舉所有比i小的索引j然後找一個長度最長的子序列去擴展。
比如元素9，我們找到它之前的元素5，9>5，而且以5結尾的LIS = [1,2,3,5]，長度最長為4。所以我們可以把9追加進這個子序列得到最長的子序列[1,2,3,5,9]，長度為5。
dp數組初始化成1，因為每個元素自己就是一個合法的、長度為1的子序列。
時間複雜度：O(n^2)
空間複雜度：O(n)
利用LIS自己本身是單調遞增的特性，我們可以進一步使用貪心+二分搜索來降低算法的時間複雜度。我們需要改變一下dp數組的定義。
dp[i] := 長度為i的LIS的末尾元素的最小值
讀起來有些拗口，別急，我們先來比較幾個子序列然後再來看為什麼要這麼定義dp數組。
ex1: A = [1, 4, 6], B = [1, 2, 3] 這兩個子序列誰比較好？當然是B好，因為如果後面出現一個數組5，就可以接在B後面構成更長的LIS，但卻不能接在A後面。所以如果長度相同，我們希望末尾元素越小越好。
ex2: A = [1, 2, 6], B = [1, 4, 6] 這兩個子序列誰比較好？答案是一樣好。因為末尾元素相同，不管後面的元素是什麼樣子，擴展A還是擴展B的結果是相同的。對於相同長度的子序列，只有末尾元素會影響決策，而和前面的元素沒有關係。
所以對於一個給定的長度LIS，我們只需要記錄該長度的子序列的末尾元素的最小值，即dp[i]。
有了這些基本思想之後我們來看一個這個算法的具體過程。
對於每個元素A[i]：
1. 如果它把當前最長的LIS的末尾元素要大，我們可以用它去擴展LIS
2. 否則我們找一個長度最長的並且末尾元素>=A[i]的LIS，去替換它的末尾元素，因為我們希望末尾元素越小越好。
由於dp數組是按照長度存儲LIS的末尾元素的，再加上其本身也是單調遞增的，所以我們可以使用二分搜索找到可以替換的元素的index。
我們直接找一個例子看一下
A: [1,4,2,3,6,5,9,4]
a
dp1
[1] // [1] 擴展長度為0的LIS
4
[1,4] // [*,4] 擴展長度為1的LIS2
[1,2] // [*,2] 更新長度為2的LIS
3
[1,2,3] // [*,*,3] 擴展長度為2的LIS
6
[1,2,3,6] // [*,*,*,6] 擴展長度為3的LIS
5
[1,2,3,5] // [*,*,*,5] 更新長度為4的LIS
9
[1,2,3,5,9] // [*,*,*,*,9] 擴展長度為4的LIS4
[1,2,3,4,9] // [*,*,*,4] 更新長度為4的LIS第一行A[i] = 1，一開始dp為空，我們直接擴展長度為0的LIS，得到長度為1的LIS = [1]。

相關焦點

  • 動態規劃求解最長公共子序列
    最長公共子序列最長公共子序列，英文為Longest Common Subsequence，縮寫LCS。一個序列，如果是某兩個或多個已知序列的最長子序列，則稱為最長公共子序列。另外，要注意的是最長公共子序列與最長公共子串不一樣，下面看一個例子就明白。有序列S1和S2，其中S1=hello，S2=hero。那麼最長公共子序列為heo，而最長公共子串為he。
  • 動態規劃解最長公共子序列問題
    1 最長公共子序列問題概述1.1 問題定義序列2 動態規劃求解最長公共子序列問題    int** C=nullptr;    //輔助矩陣    int** src=nullptr;    //使用動態規劃方法計算C矩陣和src矩陣    void writeTable(Seq* seq1,Seq* seq2);    //使用回溯方法來得到所有的最長公共子序列    void createSubSeq(Seq*
  • 詳解最長公共子序列問題,秒殺三道動態規劃題目
    動態規劃系列問題也是一樣，尤其是子序列相關的問題。本文從「最長公共子序列問題」展開，總結三道子序列問題，解這道題仔細講講這種子序列問題的套路，你就能感受到這種思維方式了。最長公共子序列計算最長公共子序列（Longest Common Subsequence，簡稱 LCS）是一道經典的動態規劃題目，大家應該都見過：給你輸入兩個字符串s1和s2，請你找出他們倆的最長公共子序列，返回這個子序列的長度。
  • LeetCode 例題精講 | 15 最長公共子序列:二維動態規劃的解法
    Longest Common Subsequence 最長公共子序列（Medium）給定兩個字符串 s 和 t，返回這兩個字符串的最長公共子序列的長度。若這兩個字符串沒有公共子序列，則返回 0。不過，打家劫舍問題是一維動態規劃問題，而還有很多題目屬於二維動態規劃。今天我們就以一道經典的「最長公共子序列」問題講解二維動態規劃的解法。最長公共子序列問題經典到什麼程度呢？經典到有自己的專用縮寫 —— LCS (Longest Common Subsequence)。
  • 深入理解動態規划算法 | 最長公共子序列LCS
    前面三篇文章已經為大家介紹了利用動態規划算法解決問題的思路以及相關的代碼實現，最為核心的就是第一步利用數學中函數的思想來建立模型，然後求解問題。這三個問題構建的數學函數都有一個共同的特徵就是所構建的函數都是一元函數即y = f(x)。
  • 動態規劃刷題篇(1) 斐波那契、爬樓梯、路徑與最長遞增子序列
    這題就引出了動態規劃中的一個重要概念：DP數組。DP數組是用來存儲當前問題的子問題的這樣一個數組。動態規劃的核心就在於：當前問題可以分解為幾個子問題。最長遞增子序列給你一個整數數組 nums ，找到其中最長嚴格遞增子序列的長度
  • 經典算法研究總結(5)-動態規划算法解最長公共子序列LCS問題
    ok，咱們馬上進入面試題第56題的求解，即運用經典的動態規划算法：2.0、LCS問題描述56.最長公共子序列。題目：如果字符串一的所有字符按其在字符串中的順序出現在另外一個字符串二中，則字符串一稱之為字符串二的子串。注意，並不要求子串（字符串一）的字符必須連續出現在字符串二中。
  • 算法總結:最長上升子序列(LIS)
    最長遞增子序列（https://leetcode-cn.com/problems/longest-increasing-subsequence/）總體思路如果你不知道最長上升子序列是什麼意思，也沒有做那道題，我——當然不會怪你 😊最長上升（遞增）子序列這道題是最最基本的，也是最常考的題了，其他題目都是由它衍生而來。
  • 算法精析:10隻白鼠試喝千瓶水1瓶有毒與最長公共子序列(串)
    四、最長公共子序列（串）算法題目：首先，最長公共子序列（LCS）及最長公共子串（LCSubstr）的定義：a="ABCGEUA"b="C五、最長公共子序列（串）算法思維分析這是一道考察動態規劃在算法中應用的題目，面試中很常見，也是一道經典的算法題。如果沒有見過類似題目的人，可能覺得有點難度。以下為思維線索分析(如果已經有所了解，請跳過)：1、求最長公共子序列及子串，可用使用暴力破解法。
  • 列印出最長的公共子序列(LCS)
    在前一課中，我們討論了最長公共子序列（LCS）問題，並且討論了如何計算兩個序列的LCS的長度，但是沒有輸出具體的LCS序列。在本課中，我們討論了如何構造和輸出LCS具體序列。【問題】給定兩個序列，請找出兩個序列中存在的最長公共子序列（LCS）。注意：子序列由原序列中的子元素組成，這些子元素的次序與它們在原序列中出現的次序一樣，但不一定連續。
  • 雖然你看過,但就是寫不出來系列-最長上升(下降)子序列並輸出子序列
    任何疑問、意見、建議請公眾號留言或聯繫qq474356284    給定一個無序的整數數組，找到其中最長上升子序列的長度。
  • 單序列與雙序列動態規劃經典題解
    reference： nine chapter algrithm本篇給出一道單序列動態規劃題解的詳細分析過程，再給一道雙序列型動態規劃
  • leetcode873_go_最長的斐波那契子序列的長度
    如果序列 X_1, X_2, ..., X_n 滿足下列條件，就說它是 斐波那契式 的：n >= 3對於所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}給定一個嚴格遞增的正整數數組形成序列，找到 A 中最長的斐波那契式的子序列的長度。如果一個不存在，返回 0 。
  • 【算法學習】動態規劃
    動態規劃的思想實質是分治思想和解決冗餘。與分治法類似的是，我們將原問題分解成若干個子問題，先求解子問題，再從這些子問題的解得到原問題的解。與分治法不同的是，經分解的子問題往往不是互相獨立的。若用分治法來解，有些共同部分被重複計算了很多次。
  • LeetCode 例題精講 | 16 最大子數組和:子數組類問題的動態規劃技巧
    要想熟練做出動態規劃題目，還要掌握足夠的解題技巧。接下來的文章中，我會講解動態規劃問題中針對不同類型問題的小技巧。今天要講的是關於「子數組」類題目的常見技巧。在講具體問題之前，我們要明確一下「子數組」和「子序列」的概念。
  • 動態規划算法Dynamic Programming
    動態規劃與分治法相似，都是通過組合子問題的解來求解原問題。不同的是，分治法將問題劃分為互不相交的子問題，遞歸的求解子問題，再將他們的解組合起來，求出原問題的解。與之相反，動態規劃應用於子問題重疊的情況，即不同的子問題具有公共的子子問題。在這種情況下，分治法會做許多不必要的工作，他會反覆求解那些公共子子問題。
  • 最長的Zig-Zag交替子序列問題
    最長的交替(Zig-Zag)子序列問題是找到給定序列的最長子序列的長度，以使該子序列中的所有元素交替出現。;22>9<49>31<60子序列{10, 22, 9, 50, 31, 60}滿足 10<22>9<50>31<60算法分析我們還是通過動態編程的方法來解決這個問題。
  • Longest Common Subsequence 最長公共子序列
    Constraints:這道題讓求最長相同的子序列，注意是子序列，不是子串，所以字符並不需要相連，但是字符順序還是需要保持的。LeetCode 之前也有題目需要藉助求 LCS 來解題，比如 Delete Operation for Two Strings，當時博主還疑惑怎麼 LeetCode 中沒有專門求 LCS 的題呢，這不，終於補上了。
  • Java動態規划算法策略
    Dynamic Programming是五大常用算法策略之一，簡稱DP，譯作中文是「動態規劃」，可就是這個聽起來高大上的翻譯坑苦了無數人，因為看完這個算法你可能會覺得和動態規劃根本沒太大關係，它對「動態」和「規劃」都沒有太深的體現。
  • 關於動態規劃,你想知道的都在這裡了
    ref=hackernoon.com）（3）最長遞增子序列給定一個未排序的整數數組，求最長遞增子序列的長度。例如，對於數組[10,9,2,5,3,7,101,18]而言，其輸出為4，即序列[2,3,7,101]解決方案我們需要找到大小為n的數組的最長遞增子序列的長度。這聽起來像是一個可以通過動態規劃來解決的優化問題，那麼讓我們來試一下。