动态规划之子数组系列（下）

等差数列划分

题目：等差数列划分

思路

• 状态表示：dp[i]表示，以i位置为结尾的所有子数组中有多少个等差数列

• 状态转移方程：在当前位置nums[i]上，若

  • 若nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]，此时构成一个新的等差数列，即dp[i] = dp[i - 1] + 1
  • 若nums[i] - nums[i - 1] != nums[i - 1] - nums[i - 2]，此时构不成一个新的等差数列，即dp[i] = 0

• 初始化：前两个位置的元素无法构成等差数列，因此初始化 dp[0] = dp[1] = 0

• 填表顺序：从左往右

• 返回值：返回整个dp 表中的所有值

C++代码

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++)
        {
            dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ? dp[i - 1] + 1 : 0;
            ret += dp[i];
        }

        return ret;
    }
};

最长湍流子数组

题目：最长湍流子数组

思路

• 状态表示：以i位置结尾的所有子数组中最长的湍流数组长度，此时结尾会有两种状态

  • i位置呈现上升趋势，记f[i]
  • i位置呈现下降趋势，记g[i]

• 状态转移方程：

  • f[i]
    • arr[i] < arr[i - 1]时，说明i位置比i - 1位置小，此时i位置无法呈现上升趋势，无法和前面结合，所以1
    • arr[i] > arr[i - 1]时，说明i位置比i - 1位置大，此时i位置呈现上升趋势，即f[i] = g[i - 1] + 1
    • arr[i] = arr[i - 1]时，无法构成构成湍流数组，所以1
  • g[i]
    • arr[i] < arr[i - 1]时，说明i位置比i - 1位置小，此时i位置呈现下降趋势，即g[i] = f[i - 1] + 1
    • arr[i] > arr[i - 1]时，说明i位置比i - 1位置大，此时i位置无法呈现下降趋势，法和前面结合，所以1
    • arr[i] = arr[i - 1]时，无法构成构成湍流数组，所以1

• 初始化：每一个元素都能构成湍流数组，所以将f和g表都初始化为1

• 填表顺序：从左往右两个表一起填

• 返回值： 返回两个数组中的最大值

C++代码

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

            ret = max(ret, max(g[i], f[i]));
        }
        return ret;
    }
};

单词拆分

题目：单词拆分

思路

• 状态表示：dp[i]表示，区间[0, i]区间内的字符串，能否被字典中的单词拼接而成

• 状态转移方程：根据最后一个位置的情况来分析，设最后一个单词起始位置为j。这样整个字符串就被划分为[0, j - 1]和[j, i]两个区间；当两个区间都满足条件时，即成立；

  • 对于[0, j - 1]，我们判断dp[j - 1]```的bool```值
  • 对于[j, i]，我们判断这个单词是否在字典中，即s.substr(j, j - i + 1)是否在字典中存在
  • 满足上述两者，dp[i] = true；否则dp[i] = false

• 初始化：添加一个辅助结点，帮助初始化。可以将字符串前面加上一个占位符 s = ' ' + s，这样就没有下标的映射关系的问题了，同时还能处理空串的情况。 dp[0] = true，表示空串能够拼接而成

• 填表顺序：从左往右

• 返回值：返回 dp[n]位置的布尔值

C++代码

class Solution 
{
public:
    bool wordBreak(string s, vector<string>& wordDict) 
    {
        unordered_set<string> hash;
        for (string& s : wordDict)
            hash.insert(s);

        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true;
        s = ' ' + s;
        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];
    }
};

环绕字符串中唯一的子字符串

题目：环绕字符串中唯一的子字符串

思路

• 状态表示：dp[i]表示以 i 位置的元素为结尾的所有子串中，有多少个在 base 中出现过

• 状态转移方程：

  • 子串的长度等于 1，此时这一个字符会出现在 base 中
  • 子串的长度大于 1，i位置和 i - 1 位置上的字符组合后，出现在 base 中
  • 如何判断组合字符出现在base中
    • s[i - 1] + 1 == s[i]，此时为顺序，即a, b，g,h
    • s[i - 1] == 'z' && s[i] == 'a'，即z,a
    • 此时dp[i] = dp[i - 1]
  • 综上，dp[i] = dp[i - 1] + 1。注意此处+1并非是对于子串长度大于1，而是统计长度等于 1和长度大于 1的总数！

• 初始化：初始化为1

• 填表顺序：从左往右

• 返回值：返回dp表中所有元素的和，但这里需要去重。所以，对于26个字母，我们统计以其为结尾的最大·。创建一个大小为26 的数组，统计所有字符结尾的最大dp 值

C++代码

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] - 1 == s[i - 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 sum = 0;
        for (int& x : hash)
            sum += x;

        return sum;
    }
};