【刷题篇】动态规划（八）

文章目录

• 1、最长定差子序列
• 2、 最长的斐波那契子序列的长度
• 3、最长等差数列
• 4、等差数列划分 II - 子序列
• 5、回文子串
• 6、最长回文子串

1、最长定差子序列

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。
子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
                    //arr  dp
        unordered_map<int,int> hash;
        hash[arr[0]]=1;
        int maxi=1;
        for(int i=1;i<arr.size();i++)
        {//hash[arr[i]-difference]没有该数就直接为0+1
            hash[arr[i]]=hash[arr[i]-difference]+1;
            maxi=max(maxi,hash[arr[i]]);
        }
        return maxi;
    }
};

2、 最长的斐波那契子序列的长度

如果序列 X_1, X_2, …, X_n 满足下列条件，就说它是 斐波那契式 的：
n >= 3
对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n=arr.size();
        unordered_map<int,int> hash;
        for(int i=0;i<n;i++)
        {
            hash[arr[i]]=i;
        }
        int maxi=2;
        //i位置的最大斐波那契子序列，dp[j][i],i>j,j是i的上一个数
        vector<vector<int>> dp(n,vector<int>(n,2));
        for(int i=2;i<n;i++)//i>j
        {
            for(int j=1;j<i;j++)
            {
                int a=arr[i]-arr[j];
                if(a<arr[j]&&hash.count(a))
                {
                    dp[j][i]=dp[hash[a]][j]+1;
                }
                maxi=max(dp[j][i],maxi);
            }
        }
        return maxi<3?0:maxi;
    }
};

3、最长等差数列

给你一个整数数组 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 是等差的。

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n=nums.size();
        unordered_map<int,int> hash;
        hash[nums[0]]=0;
        vector<vector<int>> dp(n,vector<int>(n,2));
        int maxi=2;
        //这里为什么使用固定i,枚举j,原因是因为他可能会出现一样的值，abcaij,i肯定会优先找离他近的a
        for(int i=1;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                int a=nums[i]*2-nums[j];
                if(hash.count(a))
                {
                    dp[i][j]=dp[hash[a]][i]+1;
                }
                maxi=max(maxi,dp[i][j]);
            }
            hash[nums[i]]=i;//会将前面有相同的值进行覆盖
        }
        return maxi;
    }
};

4、等差数列划分 II - 子序列

给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。
如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。
例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
再例如，[1, 1, 2, 5, 7] 不是等差序列。
数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。
例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。
题目数据保证答案是一个 32-bit 整数。

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n=nums.size();
        unordered_map<long long,vector<int>> hash;
        for(int i=0;i<n;i++)
            hash[nums[i]].push_back(i);
        vector<vector<int>> dp(n,vector<int>(n,0));
        int maxi=0;
        for(int i=2;i<n;i++)
        {
            for(int j=1;j<i;j++)
            {
                long long a=(long long)nums[j]*2-nums[i];
                if(hash.count(a))
                {
                    for(auto k :hash[a])
                    {
                        if(k<j)
                            dp[j][i]+=dp[k][j]+1;
                    }
                }
                maxi+=dp[j][i];
            }
        }
        return maxi;
    }   
};

5、回文子串

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

class Solution {
public:
    int countSubstrings(string s) {
        int n=s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        int cnt=0;
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    dp[i][j]=i+1<j?dp[i+1][j-1]:true;
                    if(dp[i][j])
                        cnt++;
                }
            }
        }
        return cnt;
    }
};

6、最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        int len=0;
        int begin=0;
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    dp[i][j]=i+1<j?dp[i+1][j-1]:true;
                }
                if(dp[i][j]&&j-i+1>len)
                {
                    len=j-i+1;
                    begin=i;
                }
            }
        }
        return s.substr(begin,len);
    }
};