前言

幾乎所有的動(dòng)態(tài)規(guī)劃問題大致可分為以下5個(gè)步驟，后續(xù)所有問題分析都將基于此

• 1.、狀態(tài)表示：通常狀態(tài)表示分為以下兩種，其中更是第一種為主。

  • 以i為結(jié)尾，dp[i] 表示什么，通常為代求問題（具體依題目而定）
  • 以i為開始，dp[i]表示什么，通常為代求問題（具體依題目而定）

• 2、狀態(tài)轉(zhuǎn)移方程

  • 以上述的dp[i]意義為根據(jù)， 通過最近一步來分析和劃分問題，由此來得到一個(gè)有關(guān)dp[i]的狀態(tài)轉(zhuǎn)移方程。

• 3、dp表創(chuàng)建，初始化

  • 動(dòng)態(tài)規(guī)劃問題中，如果直接使用狀態(tài)轉(zhuǎn)移方程通常會(huì)伴隨著越界訪問等風(fēng)險(xiǎn)，所以一般需要初始化。而初始化最重要的兩個(gè)注意事項(xiàng)便是：保證后續(xù)結(jié)果正確，不受初始值影響；下標(biāo)的映射關(guān)系。
  • 而初始化一般分為以下兩種：
    • 直接初始化開頭的幾個(gè)值。
    • 一維空間大小+1，下標(biāo)從1開始；二維增加一行/一列。

• 4、填dp表、填表順序：根據(jù)狀態(tài)轉(zhuǎn)移方程來確定填表順序。

• 5、確定返回值

一、等差數(shù)列劃分

【題目】：413. 等差數(shù)列劃分
【題目】：

?如果一個(gè)數(shù)列 至少有三個(gè)元素 ，并且任意兩個(gè)相鄰元素之差相同，則稱該數(shù)列為等差數(shù)列。例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差數(shù)列。
?給你一個(gè)整數(shù)數(shù)組 nums ，返回?cái)?shù)組 nums 中所有為等差數(shù)組的 子數(shù)組 個(gè)數(shù)。(子數(shù)組 是數(shù)組中的一個(gè)連續(xù)序列)

【示例】：

輸入：nums = [1,2,3,4]
輸出：3
解釋：nums 中有三個(gè)子等差數(shù)組：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

【分析】：
?我們可以定義dp[i]表示以i為結(jié)尾，等差數(shù)組的子數(shù)組個(gè)數(shù)。之后我們可以通過判斷（nums[i]、nums[i-1]、nums[i-2]）是否構(gòu)成等差數(shù)列，來進(jìn)一步分析

狀態(tài)轉(zhuǎn)移方程推導(dǎo)：

1. 如果nums[i]、nums[i-1]、nums[i-2]不構(gòu)成等差數(shù)列，顯然此時(shí)以i為結(jié)尾的等差數(shù)組的子數(shù)組個(gè)數(shù)為0。即dp[i] = 0;
2. 如果構(gòu)成等差數(shù)列，此時(shí)dp[i]的值至少為1。此時(shí)我們還需加上dp[i-1]的值。原因在于如果以i-1為結(jié)尾的等差數(shù)列存在，此時(shí)該等差數(shù)列公差為dp[i-1] -dp[i-2]。同時(shí)nums[i]、nums[i-1]、nums[i-2]構(gòu)成等差數(shù)列，公差也為dp[i-1] -dp[i-2]。這也意味著，以i-1為結(jié)尾的所有等差數(shù)列，在添加新增nums[i]元素后，依然是等差數(shù)列。所以狀態(tài)轉(zhuǎn)移方程為dp[i] = dp[i - 1] + 1;

細(xì)節(jié)處理：
?顯然當(dāng)i為1、2時(shí)，狀態(tài)轉(zhuǎn)移方程不適用。我們由于dp[0]、dp[1]一定構(gòu)不成等差數(shù)列，所以我們可以先將dp[0]、dp[1]先初始化為0，在從下標(biāo)2開始，從左往右填表。

【代碼編寫】：

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        int ret = 0;
        for(int i = 2; i < n; i++)
        {
            if(nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2])
                dp[i] = dp[i - 1] + 1;
            ret += dp[i];//累加所有結(jié)果
        }
        return ret;
    }
};

二、最長湍流子數(shù)組

【題目鏈接】：978. 最長湍流子數(shù)組
【題目】：

?給定一個(gè)整數(shù)數(shù)組 arr ，返回 arr 的 最大湍流子數(shù)組的長度 。如果比較符號(hào)在子數(shù)組中的每個(gè)相鄰元素對(duì)之間翻轉(zhuǎn)，則該子數(shù)組是 湍流子數(shù)組 。
?更正式地來說，當(dāng) arr 的子數(shù)組 A[i], A[i+1], …, A[j] 滿足僅滿足下列條件時(shí)，我們稱其為湍流子數(shù)組：
若 i <= k < j ：當(dāng) k 為奇數(shù)時(shí)， A[k] > A[k+1]，且當(dāng) k 為偶數(shù)時(shí)，A[k] < A[k+1]；
或 若 i <= k < j ：當(dāng) k 為偶數(shù)時(shí)，A[k] > A[k+1] ，且當(dāng) k 為奇數(shù)時(shí)， A[k] < A[k+1]。

【示例】：

輸入：arr = [9,4,2,10,7,8,8,1,9]
輸出：5
解釋：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

【分析】：
?我們定義f[i]表示以i位置為結(jié)尾，并且最后是“上升”趨勢的最長湍流子數(shù)組大??；g[i]表示以i位置為結(jié)尾，并且最后是“下降”趨勢的最長湍流子數(shù)組大小。

狀態(tài)轉(zhuǎn)移方程推導(dǎo)：
?此時(shí)以i為結(jié)尾的湍流子數(shù)組長度可能為1，或大于1。具體如下：

特殊處理：
?以i為結(jié)尾的湍流子數(shù)組中，不管最后一步是呈上升趨勢還是下降趨勢，最小長度一定為1，即nums[i]本身。所以我們?cè)趧?chuàng)建f和g表時(shí)，可以將初始值設(shè)為1。后續(xù)填表過程中，僅需考慮子數(shù)組長度大于1的情況即可??！

【代碼編寫】：

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        vector<int> f(n, 1), g(n, 1);
        int ret = 1;
        for(int i = 1; i < n; i++)
        {
            if(arr[i] > arr[i - 1])
                f[i] = g[i - 1] + 1;
            else if(arr[i] < arr[i - 1])
                g[i] = f[i - 1] + 1;
            ret = max(ret, max(f[i], g[i]));
        }
        return ret;
    }
};

三、單詞拆分

【題目鏈接】：139. 單詞拆分
【題目】：

?給你一個(gè)字符串 s 和一個(gè)字符串列表 wordDict 作為字典。如果可以利用字典中出現(xiàn)的一個(gè)或多個(gè)單詞拼接出 s 則返回 true。
?注意：不要求字典中出現(xiàn)的單詞全部都使用，并且字典中的單詞可以重復(fù)使用。

【示例】：

輸入: s = “applepenapple”, wordDict = [“apple”, “pen”]
輸出: true
解釋: 返回 true 因?yàn)?“applepenapple” 可以由 “apple” “pen” “apple” 拼接成。
注意，你可以重復(fù)使用字典中的單詞。

【分析】：
?我們可以定義dp[i]表示以i位置為結(jié)尾的子字符串是否能單詞拆分。

狀態(tài)轉(zhuǎn)移方程推導(dǎo)：

?要判斷從下標(biāo)從0到i的子串是否能單詞拆分。我們可以將0到i的字串分為兩部分：0到j(luò)-1，j到i（0 <= j <= i）。而dp[j-1]表示以j-1位置為結(jié)尾的字串能否單詞拆分的結(jié)果。此時(shí)我們還需判斷下標(biāo)從j到i的字串是否能單詞拆分。此時(shí)即可判斷此種分發(fā)是否能實(shí)現(xiàn)單詞拆分！！
?但由于j的位置不確定。所以我們可以一次將j從開始，逐漸減小到起始下標(biāo)0。在每次遞減過程中，只有存在一種拆分發(fā)將拆分出的兩個(gè)字串都能實(shí)現(xiàn)拆分單詞，此時(shí)dp[i]=true,同時(shí)可停止遍歷。否則為false;

細(xì)節(jié)處理：
?在填dp表過程中，dp[i]的值會(huì)用到dp[j-1]（0<=j<=i）,可能會(huì)發(fā)生越界訪問。所以我們?yōu)閐p表額外增加一個(gè)空間，同時(shí)為了保證后續(xù)填表的正確性，我們需要將dp[0]初始化為true。
?同時(shí)面對(duì)字符串問題時(shí)，通常需要存在子字符竄問題。此時(shí)，下標(biāo)映射關(guān)系可能+1,可能減1。所以這里個(gè)原始字符串最開始任意增加一個(gè)字符（習(xí)慣上該字符為空字符），讓原始字符串下標(biāo)統(tǒng)一向后移動(dòng)一位。
【代碼編寫】：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_map<string, int> hash;
        for(auto& str : wordDict)//后續(xù)快速查找是否存在某單詞
            hash[str]++;
        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true;//初始化，保證后續(xù)填表正確
        s = ' ' + s;//讓s下標(biāo)集體向后移動(dòng)一位
        for(int i = 1; i <= n; i++)
            for(int j = i; j >= 1; j--)
            {
                if(dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    break;
                }
            }
        return dp[n];
    }
};

四、環(huán)繞字符串中唯一的子字符串

【題目鏈接】：467. 環(huán)繞字符串中唯一的子字符串
【題目】：

【代碼編寫】：

?定義字符串 base 為一個(gè) “abcdefghijklmnopqrstuvwxyz” 無限環(huán)繞的字符串，所以 base 看起來是這樣的：

• “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”。
  給你一個(gè)字符串 s ，請(qǐng)你統(tǒng)計(jì)并返回 s 中有多少 不同非空子串 也在 base 中出現(xiàn)。

【示例】：

輸入：s = “zab”
輸出：6
解釋：字符串 s 有六個(gè)子字符串 (“z”, “a”, “b”, “za”, “ab”, and “zab”) 在 base 中出現(xiàn)。

【分析】：
?我們可以定義dp[i]表示以i位置為結(jié)尾的字符串中非空字串在base中出現(xiàn)的個(gè)數(shù)。

狀態(tài)轉(zhuǎn)移方程推導(dǎo)：
?非空字串存在于base中有兩種可能：

1. 相鄰字符是連續(xù)的，即s[i-1] + 1 == s[i]。
2. 相鄰字符分別是26個(gè)小寫字母的結(jié)束和開始，即是bashs[i-1] == 'z' && s[i] == 'a'。
   所以狀態(tài)轉(zhuǎn)移方程為：

if((s[i] - s[i - 1] == 1) || (s[i - 1] == 'z' && s[i] == 'a'))
     dp[i] = dp[i - 1] + 1;

細(xì)節(jié)處理：
?由于當(dāng)個(gè)字符一定存在于base中，所以dp[i]的值最小為1，所以我們可以將dp表中的初始值全部初始化為1。

?上述dp表中的結(jié)果存在重復(fù)值，不能直接累加。那如何去重？

• 我們知道以某一個(gè)字符為結(jié)尾的子串中，長子串一定包含了短子串的所有結(jié)果。所以我們可以借助一個(gè)26空間大小的數(shù)組，將s分割出的字串中，以結(jié)尾字符為依據(jù)，將最長字串結(jié)果放入對(duì)應(yīng)的數(shù)組空間中。從而實(shí)現(xiàn)去重效果。即：hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
  ?既然以及去重了，最后只需將數(shù)組中的結(jié)果累加即可！！

?
【代碼編寫】：文章來源地址http://www.zghlxwxcb.cn/news/detail-850543.html

class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int n = s.size();
        vector<int> dp(n, 1);
        for(int i = 1; i < n; i++)
            if((s[i] - s[i - 1] == 1) || (s[i - 1] == 'z' && s[i] == 'a'))
                dp[i] = dp[i - 1] + 1;
        
        int hash[26] = {0};
        for(int i = 0; i < n; i++)//去重
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);

        int ret = 0;
        for(auto x : hash)
            ret += x;
        return ret;
    }
};

到了這里，關(guān)于算法沉淀——?jiǎng)討B(tài)規(guī)劃篇（子數(shù)組系列問題（下））的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！