目錄

引言：

例題1：最長遞增子序列

例題2：最長定差子序列

例題3：最長的斐波那契子序列的長度

例題4：最長等差數(shù)列

例題5：等差數(shù)列劃分II-子序列

結(jié)語：

引言：

要想解決子序列問題那么就要理解子序列和子數(shù)組的區(qū)別，二者的定義如下。

子序列：是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7]?是數(shù)組?[0,3,1,6,2,2,7]?的子序列。

子數(shù)組：是數(shù)組中的一個連續(xù)部分[6,2,2,7]?是數(shù)組?[0,3,1,6,2,2,7]?的子數(shù)組。

本節(jié)和之前的分析思路一樣還是考慮好1. 狀態(tài)表示，2.狀態(tài)轉(zhuǎn)移方程，3.初始化，4.填表順序，5.返回值。希望友友們看完本章后，自己理解一下子數(shù)組問題和子序列問題的差別。

例題1：最長遞增子序列

鏈接：最長遞增子序列

題目簡介：

給你一個整數(shù)數(shù)組?nums?，找到其中最長嚴(yán)格遞增子序列的長度。

子序列?是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7]?是數(shù)組?[0,3,1,6,2,2,7]?的子序列。

解法（動態(tài)規(guī)劃）：

?1. 狀態(tài)表示：

這里和子數(shù)組的表示方法倒是差不多。

dp[i] 表示：以i 位置元素為結(jié)尾的所有?序列中，最長遞增子序列的長度。

?2.狀態(tài)轉(zhuǎn)移方程：

推狀態(tài)轉(zhuǎn)移方程時可以畫圖幫助我們理解，下面這些情況可以大致分為兩種，一種就只有一個i還有一種i會跟在i - 1，2，3的某一個后面（子序列）。

對于dp[i] ，我們可以根據(jù)子序列的構(gòu)成?式，進(jìn)?分類討論：

（1）子序列長度為1 ：只能自己玩了，此時dp[i] = 1 。

（2）子序列長度大于1 ： nums[i] 可以跟在前面任何?個數(shù)后面形成子序列。?設(shè)前面的某?個數(shù)的下標(biāo)為j ，其中0 。只要nums[j] < nums[i] ， i 位置元素跟在j 元素后?就可以形成遞增序列，長度為dp[j] + 1 。因此，我們僅需找到滿足要求的最大的dp[j] + 1 即可。

綜上， dp[i] = max(dp[j] + 1, dp[i]) ，其中0 <= j <= i - 1 && nums[j] < nums[i]。

?3.初始化：

在求長度之類的dp問題一般可以直接把dp表都初始化成1，因為在我們的狀態(tài)表示中長度至少為1.因此可以將dp 表內(nèi)所有元素初始化為1 。

?4.填表順序：

從左往右

?5.返回值：?

由于不知道最長遞增子序列以誰結(jié)尾，因此返回dp 表里面的最大值。

代碼如下：

class Solution {
    public int lengthOfLIS(int[] nums) {
        //1.創(chuàng)建 dp 表
        //2.初始化
        //3.填表
        //4.返回值
        int n = nums.length;
        int[] dp = new int[n];
        for(int i = 0;i < n;i++){
            dp[i] = 1;
        }
        int max = dp[0];
        for(int i = 1;i < n;i++){
            for(int j = i - 1;j >= 0;j--){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

時間復(fù)雜度：O（n^2）

空間復(fù)雜度：O（n）

接下來幾題會用到動態(tài)規(guī)劃 + 哈希表

例題2：最長定差子序列

鏈接：最長定差子序列

題目簡介：

給你一個整數(shù)數(shù)組?arr?和一個整數(shù)?difference，請你找出并返回?arr?中最長等差子序列的長度，該子序列中相鄰元素之間的差等于?difference?。

子序列?是指在不改變其余元素順序的情況下，通過刪除一些元素或不刪除任何元素而從?arr?派生出來的序列。

?解法（動態(tài)規(guī)劃）：

這道題和最長遞增子序列有?些相似，但仔細(xì)讀題就會發(fā)現(xiàn)，本題的arr.lenght?達(dá)10^5 ，使?O(N^2) 的lcs 模型?定會超時。那么，它有什么信息是不同于最長遞增子序列呢？是定差。之前，我們只知道要遞增，不知道前?個數(shù)應(yīng)當(dāng)是多少；現(xiàn)在我們可以計算出前?個數(shù)是多少了，就可以?數(shù)值來定義dp 數(shù)組的值，并形成狀態(tài)轉(zhuǎn)移。這樣，就把已有信息有效地利用了起來。

?1. 狀態(tài)表示：

dp[i] 表示：以i 位置的元素為結(jié)尾所有的子序列中，最長的等差子序列的長度。

?2.狀態(tài)轉(zhuǎn)移方程：

對于dp[i] ，上?個定差?序列的取值定為arr[i] - difference 。只要找到以上?個數(shù)字為結(jié)尾的定差?序列?度的dp[arr[i] - difference] ，然后加上1 ，就是以i為結(jié)尾的定差?序列的?度。

這里要考慮一個問題：如果在i前面有多個等于arr[i] - difference的dp值要取哪一個呢？

?其實取最后一個即可，因為最后一個肯定大于等于前面幾個的長度。

因此，這?可以選擇使?哈希表做優(yōu)化。我們可以把【元素， dp[j]】綁定，放進(jìn)哈希表（會覆蓋）中。甚?不?創(chuàng)建dp 數(shù)組，直接在哈希表中做動態(tài)規(guī)劃。

?3.初始化：

剛開始的時候，需要把第?個元素放進(jìn)哈希表中， hash[arr[0]] = 1。

?4.填表順序：

從左往右

?5.返回值：

返回整個dp 表中的最?值

代碼如下：

這里之所以不用 hash[arr[0]] = 1，是因為在下面put的寫法中已經(jīng)包含了。

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        //在哈希表里面做動態(tài)規(guī)劃
        Map<Integer,Integer> map = new HashMap<>();
        int ret = 1;
        for(int x:arr){
            map.put(x,map.getOrDefault(x - difference,0) + 1);
            ret = Math.max(ret,map.get(x));
        }
        return ret;
    }
}

?時間復(fù)雜度：O（n）?

?空間復(fù)雜度：O（n）

例題3：最長的斐波那契子序列的長度

鏈接：最長的斐波那契子序列的長度

題目簡介：

如果序列?X_1, X_2, ..., X_n?滿足下列條件，就說它是?斐波那契式?的：

• n >= 3
• 對于所有?i + 2 <= n，都有?X_i + X_{i+1} = X_{i+2}

給定一個嚴(yán)格遞增的正整數(shù)數(shù)組形成序列 arr?，找到?arr?中最長的斐波那契式的子序列的長度。如果一個不存在，返回??0 。

（回想一下，子序列是從原序列?arr?中派生出來的，它從?arr?中刪掉任意數(shù)量的元素（也可以不刪），而不改變其余元素的順序。例如，?[3, 5, 8]?是?[3, 4, 5, 6, 7, 8]?的一個子序列）

?解法（動態(tài)規(guī)劃）：

?1. 狀態(tài)表示：

?2.狀態(tài)轉(zhuǎn)移方程：

設(shè)nums[i] = b, nums[j] = c ，那么這個序列的前?個元素就是a = c - b 。我們根據(jù)a 的情況討論：

（1）a 存在，下標(biāo)為k ，并且a < b ：此時我們需要以k 位置以及i 位置元素為結(jié)尾的最?斐波那契?序列的?度，然后再加上j位置的元素即可。于是dp[i][j] = dp[k][i] + 1。

（2）a 存在，但是b < a < c ：此時只能兩個元素自己玩了， dp[i][j] = 2 。

（3）a 不存在：此時依舊只能兩個元素自己玩了， dp[i][j] = 2 。

優(yōu)化點：我們發(fā)現(xiàn)，在狀態(tài)轉(zhuǎn)移?程中，我們需要確定a 元素的下標(biāo)。因此我們可以在dp 之前，將所有的元素+下標(biāo)綁定在?起，放到哈希表中。

?3.初始化：

可以將表??的值都初始化為2

?4.填表順序：

先固定最后?個數(shù)，然后枚舉倒數(shù)第二個數(shù)。由于j > i 故表如下：

?5.返回值：

因此返回dp 表中的最大值但是最大值可能小于3 ，小于3的話說明不存在。因此需要判斷?下。

具體代碼如下：

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        //1.創(chuàng)建 dp 表
        //2.初始化
        //3.填表
        //4.返回值
        Map<Integer,Integer> map = new HashMap<>();
        int n = arr.length;
        for(int i = 0;i < n;i++){
            map.put(arr[i],i);
        }
        int[][] dp = new int[n][n];
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                dp[i][j] = 2;
            }
        }
        int ret = 2;
        for(int j = 2;j < n;j++){
            for(int i = 1;i < j;i++){
                int a = arr[j] - arr[i];
                if(a < arr[i] && map.containsKey(a)){
                    dp[i][j] = dp[map.get(a)][i] + 1;
                }
                ret = Math.max(ret,dp[i][j]);
            }
        }
        return ret < 3 ? 0 : ret;
    }
}

時間復(fù)雜度：O（n^2）

空間復(fù)雜度：O（n^2）

例題4：最長等差數(shù)列

鏈接：最長等差數(shù)列

題目簡介：

給你一個整數(shù)數(shù)組?nums，返回?nums?中最長等差子序列的長度。

回想一下，nums?的子序列是一個列表?nums[i1], nums[i2], ..., nums[ik]?，且?0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果?seq[i+1] - seq[i](?0 <= i < seq.length - 1) 的值都相同，那么序列?seq?是等差的。

?解法（動態(tài)規(guī)劃）：

?1. 狀態(tài)表示：

和上一題一樣，一維的dp表不能解決問題，dp[i][j] 表示：以i 位置以及j位置的元素為結(jié)尾的所有的子序列中，最長的等差序列的長度。規(guī)定?下i < j 。

?2.狀態(tài)轉(zhuǎn)移方程：

設(shè)nums[i] = b, nums[j] = c ，那么這個序列的前?個元素就是a = 2 * b - c 。我們根據(jù)a的情況討論：這里和例題3的分析差不多就直接給圖了。

優(yōu)化點：我們發(fā)現(xiàn)，在狀態(tài)轉(zhuǎn)移?程中，我們需要確定a 元素的下標(biāo)。因此我們可以將所有的元素+?下標(biāo)綁定在?起，放到哈希表中，這里有兩種策略：

（1）在dp 之前，放?哈希表中。這是可以的，但是需要將下標(biāo)形成?個數(shù)組放進(jìn)哈希表中。這樣 時間復(fù)雜度較高，我?guī)?家試過了，超時。

（2）?邊dp ，?邊保存。這種方式，我們僅需保存最近的元素的下標(biāo)，不用保存下標(biāo)數(shù)組。但是 ?這種?法的話，我們在遍歷順序那里，先固定倒數(shù)第?個數(shù)（i），再遍歷倒數(shù)第?個數(shù)（j）。這樣就可以在i 使用完時候，將nums[i] 扔到哈希表中。?

?3.初始化：

將所有位置初始化為2。

?4.填表順序：

因為這里要保證去相同a下標(biāo)k的最大值。

下圖為固定倒數(shù)第一個數(shù)（j），枚舉倒數(shù)第二個數(shù)。這樣就不能保證跟新dp表時用到的a為在i前面的。紅色部分為a可能出現(xiàn)的地方。

所以我們采用先固定倒數(shù)第?個數(shù)，然后枚舉倒數(shù)第?個數(shù)如下圖，這樣a就只能在i的前面。

?5.返回值：

返回dp 表中的最大值

代碼如下：

class Solution {
    public int longestArithSeqLength(int[] nums) {
        //1.創(chuàng)建 dp 表
        //2.初始化
        //3.填表
        //4.返回值
        Map<Integer,Integer> map = new HashMap<>();
        int n = nums.length;
        map.put(nums[0],0);
        int[][] dp = new int[n][n];
        for(int i = 0;i < n;i++){
            Arrays.fill(dp[i],2);
        }
        int ret = 2;
        for(int i = 1;i < n;i++){
            for(int j = i + 1;j < n;j++){
                int a = 2 * nums[i] - nums[j];
                if(map.containsKey(a)){
                    dp[i][j] = dp[map.get(a)][i] + 1;
                    ret = Math.max(ret,dp[i][j]);
                }
            }
            map.put(nums[i],i);
        }
        return ret;

    }
}

時間復(fù)雜度：O（n^2）

空間復(fù)雜度：O（n^2）

例題5：等差數(shù)列劃分II-子序列

鏈接：等差數(shù)列劃分II-子序列

題目簡介：

給你一個整數(shù)數(shù)組?nums?，返回?nums?中所有?等差子序列?的數(shù)目。

如果一個序列中?至少有三個元素?，并且任意兩個相鄰元素之差相同，則稱該序列為等差序列。

• 例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7]?和?[3, -1, -5, -9]?都是等差序列。
• 再例如，[1, 1, 2, 5, 7]?不是等差序列。

數(shù)組中的子序列是從數(shù)組中刪除一些元素（也可能不刪除）得到的一個序列。

• 例如，[2,5,10]?是?[1,2,1,2,4,1,5,10]?的一個子序列。

題目數(shù)據(jù)保證答案是一個?32-bit?整數(shù)。

??解法（動態(tài)規(guī)劃）：

?1. 狀態(tài)表示：

dp[i][j] 表?：以i 位置以及j 位置的元素為結(jié)尾的所有的?序列中，等差子序列的個數(shù)。規(guī)定?下i < j 。這一類問題基本都這樣。

?2.狀態(tài)轉(zhuǎn)移方程：

設(shè)nums[i] = b, nums[j] = c ，那么這個序列的前?個元素就是a = 2 * b - c 。我們根據(jù)a的情況討論：（還是這張圖非常重要）

（1）a 存在，下標(biāo)為k ，并且a < b ：此時我們知道以k 元素以及i 元素結(jié)尾的等差序列的數(shù)dp[k][i] ，在這些?序列的后?加上j 位置的元素依舊是等差序列。但是這?會多出來?個以k, i, j 位置的元素組成的新的等差序列，因此dp[i][j] = dp[k][i] + 1。

（2）因為a 可能有很多個，我們需要全部累加起來。

綜上， dp[i][j] += dp[k][i] + 1 。

優(yōu)化點：我們發(fā)現(xiàn)，在狀態(tài)轉(zhuǎn)移?程中，我們需要確定a 元素的下標(biāo)。因此我們可以在dp之前，將【所有元素+下標(biāo)數(shù)組】綁定在?起，放到哈希表中。這?為何要保存下標(biāo)數(shù)組，是因為我們要統(tǒng)計個數(shù)，所有的下標(biāo)都需要統(tǒng)計，之前是覆蓋。

?3.初始化：

初始化dp 表為0。

?4.填表順序：

先固定倒數(shù)第?個數(shù)，然后枚舉倒數(shù)第?個數(shù)（這里就不能先固定倒數(shù)第二個數(shù)，因為要的是各個情況的和而不是最大值）。

?5.返回值：

我們要統(tǒng)計所有的等差子序列，因此返回dp 表中所有元素的和。

代碼如下：

這里特別說明一個，題目給出的數(shù)都是32位以內(nèi)的但是相加減可能會越界（??），有些例子越界后可能會正好形成等差數(shù)列從而報錯（我替你們試過了??????），故要設(shè)置成long類型。

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        //1.創(chuàng)建 dp 表
        //2.初始化
        //3.填表
        //4.返回值
        Map<Long,List<Integer>> map = new HashMap<>();
        int n = nums.length;
        int[][] dp = new int[n][n];
        for(int i = 0;i < n;i++){
            long cmp = (long)nums[i];
            if(!map.containsKey(cmp)){
                map.put(cmp,new ArrayList<Integer>());
            }
            map.get(cmp).add(i);
        }
        int sum = 0;
        for(int j = 2;j < n;j++){
            for(int i = 1;i < j;i++){
                long a = 2L * nums[i] - nums[j];
                if(map.containsKey(a)){
                    for(int k : map.get(a)){
                        if(k < i){
                            dp[i][j] += dp[k][i] + 1;
                        }
                    }
                }
                sum += dp[i][j];
            }
        }
        return sum;

    }
}

時間復(fù)雜度：O（n^2）

空間復(fù)雜度：O（n^2）

結(jié)語：

其實寫博客不僅僅是為了教大家，同時這也有利于我鞏固知識點，和做一個學(xué)習(xí)的總結(jié)，由于作者水平有限，對文章有任何問題還請指出，非常感謝。如果大家有所收獲的話還請不要吝嗇你們的點贊收藏和關(guān)注，這可以激勵我寫出更加優(yōu)秀的文章。文章來源地址http://www.zghlxwxcb.cn/news/detail-839269.html

到了這里，關(guān)于動態(tài)規(guī)劃課堂5-----子序列問題（動態(tài)規(guī)劃 + 哈希表）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！