最喜欢dp动态规划的一次(暑期刷题)
前言
所有的问题可能不止一种方法，但是由于是dp专题，只会讲述dp解题的方法。如果需要别的算法可以看看后续的更新。 同时，这里的dp算法并不一定是最简单的效率最高的解题方法，可能别的算法更适合更方便。
1、环绕字符串中唯一的子字符串
题目链接在这 题目概念解析： 由题意得，定义的字符串base不难发现，这是又“…zabcdefg…”本身的字母表来进行排序的，只不过是首尾相连的环绕形态的。所以知道了基本的base的构成，我们进一步来看题目。 题目会给一个字符串，让我们从字符串中找到能够符合base顺序的非空子串的个数。首先，非空子串的个数就不少并且还要满足符合base的条件。那么这个问题是能够利用dp动态规划来帮助我们解决的。 解题过程： 动态规划最最重要的莫过于是状态转移方程，确定好状态转移方程就差不多能够解决问题。 状态转移方程定义是更具不同的问题来确定，这道题目，状态转移方程完全可以是dp[i]表示从开始位置到i位置符合条件的子字符串能有多少。 题目做后返回的答案并不是dp[n]，应该是从0到n位置之间所有的符合条件的子数组相加。 但是但是！答案并不只是单纯的数字相加，因为26个字母可能在计算的过程中有重复的字母为结尾，这样的话会多算很多，所以这种情况还是需要注意一下的。 怎么解决重复问题？利用hash来确保统计的是唯一一次，如果不是，两者相互比较，较长的才保留较短的忽视。 解题代码：
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]+1==s[i]||(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 e:hash)
{
ret+=e;
}
return ret;
}
};2、最长递增子序列
题目链接在这 题目概念解析： 最长的递增子序列顾名思义，在这段数组中找到一个最长的递增子序列，同时这里的子序列没必要是连续的，这也很重要。 解题过程： 这题我有两种方法吧，但是既然在动态规划的文章中的话，那就先讲动态规划吧。(还有一种方法是贪心) 状态转移方程定义，从0开始到i位置到时候的最长递增子序列长度。 那也是很简单啊。那状态转移方程怎么写呢？假设是在第i个位置，让j从i-1开始，但是要保证j>=0的状态。如果原数组中的j位置小于i位置的话，比较一下dp[j]+1和dp[i]的大小，大的保留。 其中重要的是ret的初始值是1，dp所有元素的初始大小也是1，因为本身一个数也能是一个子序列，也是递增的子序列。 解题代码：
class Solution {
public:
int lengthOfLIS(vector<int>& nums)
{
int n=nums.size();
vector<int>dp(n,1);
int ret=1;
for(int i=1;i<n;i++)
{
for(int j=i-1;j>=0;j--)
{
if(nums[i]>nums[j])
dp[i]=max(dp[i],dp[j]+1);
}
ret=max(dp[i],ret);
}
return ret;
}
};3、摆动序列
题目链接在这 题目概念解析： 其实题目前提说的特殊情况，写完了也能够发现居然不需要修改也能够直接通过。大概的意思就是这个所谓的“摆动序列”是意味着数组在x，y表格上是波动的。不一定必须要把差值算完之后再来求解，其实直接的利用两个数之间的大小就能够相互比较。 解题过程： 最长的摆动数组是怎么摆动的？开始是先有向上的趋势还是先有向下的趋势？所以不得不增加两个dp的数组来记录，一个单独来记录开始是上升的，一个来记录开始是下降的。 dp数组初始元素还是1，因为最短最坏的情况还是本身的长度。 状态转移方程还是到i位置的最长摆动数组的长度。(最重要的是能够想到两个数组来简化问题) 定义的两个数组需要清楚哪一个是记录最后一个是上增，哪一个是记录做后一个是下降的长度。 细节问题是当两个数相等的时候是不能有操作的，只有大于或者小于才能比较啊，dp数组更新啊。 解题代码：
class Solution {
public:
int wiggleMaxLength(vector<int>& nums)
{
int n=nums.size();
int ret=1;
vector<int>g(n,1),f(n,1);
for(int i=1;i<n;i++)
{
for(int j=i-1;j>=0;j--)
{
if(nums[i]>nums[j])f[i]=max(f[i],g[j]+1);
else if(nums[i]<nums[j])
g[i]=max(g[i],f[j]+1);
ret=max(f[i],g[i]);
}
}
return ret;
}
};其中的思想和上一题差不多，确定结尾之后向前进行查找，找到了之后，判断时候需要更新，比较两个dp的长度。思想差不多，但是可能想出来有点困难，但是举一反三很重要。
4、最长递增子序列的个数
题目链接在这 题目概念解析： 很关键啊，很关键，这是一道稍微不注意就可能混淆的题目，题目要求是找到最长的子序列的同时也计算出最长的子序列的长度。一个大问题可以分解为两个小问题。 问题一：找到最长子序列 。 问题二：找到最长子序列个数。 解题过程： 由于长度和个数的不确定性，我们需要两个数组和一个变量来帮助我们。 count与len数组是动态规划的数组，其中的含义分别表示的是从0到i位置最长数组的个数和最长数组的长度。注意！这里到i位置结尾的并不一定就是现在循环到i位置最长的子序列。所以还需要单独的变量来记录最长的长度和个数。 retcount表示的是问题答案，最长递增序列的个数。retlen表示最长子序列的长度。 在每次循环的时候比较retlen和len[i]的长度，如果retlen更长的话不需要改变，如果retlen和len[i]相等的话就retcount需要增加ret[i]个，如果retlen小于len[i]的话就需要更新retlen并且更新retcount的个数。当然retcount不是更新为1，而是更新为count[I]的个数。这也是需要值得注意的地方！ 解题代码：
class Solution {
public:
int findNumberOfLIS(vector<int>& nums)
{
int n=nums.size();
vector<int>count(n,1),len(n,1);
int retlen=1,retcount=1;
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(nums[i]>nums[j])
{
if(len[i]<len[j]+1)
{
count[i]=count[j];
len[i]=len[j]+1;
}
else if(len[i]==len[j]+1)
{
count[i]+=count[j];
}
}
}
if(retlen==len[i])
{
retcount+=count[i];
}
else if(retlen<len[i])
{
retlen=len[i];
retcount=count[i];
}
}
return retcount;
}
};5、最长数对链
题目链接在这 题目概念解析： 就是让一个数对能够从小到大的排序并且还是最长的。 解题过程： 通过前面几个的问题的解决，我觉的这个dp问题很简单啊，这无需多说，顶多要注意的就是比较的顺序和开始时候的排序是重点。 解题代码：
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs)
{
sort(pairs.begin(),pairs.end());
int n=pairs.size();
vector<int>dp(n,1);
int ret=1;
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(pairs[i][0]>pairs[j][1])
dp[i]=max(dp[j]+1,dp[i]);
}
ret=max(ret,dp[i]);
}
return ret;
}
};6、最长定差子序列
题目链接在这里 题目概念解析： 这题看上去是直接能够用上面的方法来解决，可是可惜的是我写了，最后一个用例超时了，因为测试用例范围已经很明确了是有足足105个数，如果真正的用之前的方法，那可是O(N2)的时间复杂度，这样的话最后会超过时间限制，那么该怎么解决呢？ 解题思路： 由于定差子序列，说明相差的数值是一样的，那么解决问题的关键就是这里的定差。怎么利用定差呢？ 知道最后一个元素，能够推断倒数第二个，以此类推。所以这一步很重要。所以由于能够直接推断，我能够构建一个hash表来帮助我们，将数组中的数arr[i]与dp[i]进行绑定，能够直接用O(1)的时间复杂度直接来进行访问。这个优化是建立在定差子序列的前提，是定差。还能够再优化，直接将动态规划放在hash表中进行，省略掉dp数组。这样的话直接从N2变为了N的时间复杂度，这样也就不会超时了。 hash[arr[i]]的值的含义就是以arr[i]为结尾的值的最长定差子序列的长度。 解题代码：
class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference)
{
int n=arr.size();
int ret=1;
unordered_map<int,int>hash;
hash[arr[0]]=1;
for(int i=1;i<n;i++)
{
hash[arr[i]]=hash[arr[i]-difference]+1;
ret=max(hash[arr[i]],ret);
}
return ret;
}
};7、最长的斐波那契子序列的长度
题目链接在这 题目概念解析： 需要找到一个类似于斐波那契结构的子序列。必须要找到符合条件的。 解题过程： 由于不再是限制前一个的数，而是限制两个数，怎么样才能完成这样的操作呢？这样的要求其实影响的就是怎么样处理状态转移方程的问题变难了。因为想之前的直接dp[i]的话不能够保证在前一个数在这个最长的dp[i]中。 如果能够知道最后两个数是多少的话，能够直接推出前面的数每一个分别是多少。 所以！二维dp表来了！二维dp表的含义是 dp[i][j]:表示以i和j结尾的斐波那契子序列的最长的长度。 这样同时也能够确定这个斐波那契数列的具体状态，非常好！ 但是其中还有一些小问题，那就是对于由i和j推导出来的那个数的位置在哪？ 三种情况，1、在i和j之前的位置 2、在i和j之间的位置 3、不存在。 当是第三种情况的时候dp的数值也还是2，因为最起码的长度就是这两个i和j。 当是第二种情况的时候，由于位置的错误所以最后的结果也还是等于2。 最麻烦的还是情况一，这个时候就需要利用转移状态方程来求解。dp[i][j]=dp[k][i]+1,这就是最最重要的dp转移方程。 优化：将数组中的元素和下表绑定，能够实现在O(1)的时间复杂度下解决问题！(很庆幸，这个数组在题目定义的时候就是严格递增的，所以不用考虑元素重复的情况) 除此之外，不需要每次都进行max比较dp[i][j]的大小，因为上一个数是固定的不会改变。所以也就没有比较大小这一说辞了。 解题代码：
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr)
{
int ret=2;
int n=arr.size();
unordered_map <int,int>hash;
for(int i=0;i<n;i++)
{
hash[arr[i]]=i;
}
vector<vector<int>>dp(n,vector<int>(n,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]&&hash.count(a))
dp[i][j]=dp[hash[a]][i]+1;
ret=max(ret,dp[i][j]);
}
}
if(ret<3)
return 0;
return ret;
}
};8、总结
第一次来做一个这样子的解题的文章，可能会有些不好的地方，如果有建议的话可以在评论区留言，我会及时查看并且在下一次的文章中进行改进。 并且由于dp难度普遍是medium级别的，所以做起来会有一些吃力，同时呢，又由于dp解题方法或者是我个人的解释方法不方便理解，可能会造成一些困惑，还希望各位能够结合代码来进行进一步的理解。后续还会有别的专题的文章，请多多关注和点赞，谢谢各位了！
腾讯云开发者
