dp算法第三天(暑期提升)
善用每一分钟，作为开启未来快乐之门的钥匙。——马尔登
二维dp解决问题
1、前言
根据前两次的dp算法的实践，相信我们已经能够通过dp表示不同的含义能够解决不同的问题。但是这些dp问题对于dp算法来说还是不够，所以接下来继续学习一些关于能够利用dp来解决的问题。
2、单词拆分(开胃小菜)
题目链接在这 题目解析： 主要目的就是所给的单词串能不能由给的单词表组合而成，起始看上去是挺复杂的第一眼，但是经过前面两轮的dp训练之后应该也不算是问题。 首先我们根据经验假设，dp[i]表示的就是以i位置为结尾的字符串能否能够满足单词拆分的要求(这样子的假设就能够得出结果)。那就当以i位置为结尾的时候，我们怎么判断是否能够满足条件呢？ 状态转移方程：需要判断i位置是否能够满足我们需要从i位置向前找，找到j位置，字符串s从j到i位置到子字符需要满足存在于wordDict的字典之中，并且dp[j-1]还需要是true的情况之下才能够满足dp[i]是真的条件。其中找是否存在字典中需要的是提前先把wordDict遍历一遍，存在hash表中，这样的话，就能够实现O(1)的时间复杂度查找，总的时间复杂度也只会是O(N)，从O(N2)减少那么多事很可以的。 解题代码：
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict)
{
unordered_map<string,int>hash;
for(auto& x:wordDict)
hash[x]++;
int n=s.size();
s=" "+s;
vector<bool>dp(n+1);
dp[0]=true;
for(int i=1;i<=n;i++)
{
for(int j=i;j>=1;j--)
{
if(dp[j-1]&&hash[s.substr(j,i-j+1)])
{
dp[i]=true;
break;
}
}
}
return dp[n];
}
};3、最长回文子串
这篇文章中包含了回文串的基本做法的介绍 可以先看一看别的做法，但是dp做法虽然有点时候会把时间复杂度和空间复杂度提升上去，但是呢，这种方法有时候能够将一些困难的题目简单化，稍微有一些模版的感觉从而减少一点难度并且有的时候dp算法才是解决这类问题的百试不厌的好方法(能够确保解决问题的好方法) 题目链接在这里 题目解析： 由于是最长的子串，那就说明一定是要连在一块的，那连在一块的本质上说的也就是说我们可以利用我这里介绍的回文串这题的基础上改进，就能够解决这道题目。 怎么改进呢？首先我们需要设置一个length来表示最长的长度，其次本质上的dp表表示的含义我们不修改，就是表示i到j能否能形成一个回文串。下面这就是和之前不一样的地方了。当我们判断得出dp表此时的值是true的时候，我们需要比较一下length和j-i+1哪一个长，如果后面的长度话，我就需要改变一下length长度，同时还需要记录下i的位置，方便后续的时候substr的时候找到起始的位置。 解题代码：
class Solution {
public:
string longestPalindrome(string s)
{
int n=s.size();
int length=0;
int left=0;
vector<vector<int>>dp(n,vector<int>(n));
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])
{
if(length<j-i+1)
{
length=j-i+1;
left=i;
}
}
}
}
return s.substr(left,length);
}
};4、最长回文子序列(子串升级版)
题目链接在这 题目解析： 我们根据经验来说的话，定义一个dp表，那么dp[i]表示的就应该最好是从0到i位置为结尾的情况下，最长的回文子串的长度是多长。但是如果是这样定义的情况的话，会有缺陷。 缺陷就是不知道前面最长的回文子串具体是什么，不知道具体是什么的话就不能通过一个一个加上来的字符来判断最长子串是否会变长或者是没影响，这些都不能知道。那么这个时候不妨设置一个二维dp表来帮助我们判断，此时dp[i][j]表示的就是i到j位置的最长的子串为多长。这样的话，就能够解决问题了。 状态转移方程：首先基本的解决问题的dp表我能够确定了，那么此时的话就需要确定状态转移方程的具体是这么转移的。 当i==j的时候，dp[i][j]=1。 当i+1 ==j&&s[i]==s[j] 的时候，dp[i][j]=2。 当i+1<j && s[i]==s[j]的时候,dp[i][j]=2+dp[i+1][j-1] 当i+1<j 但是 s[i]!=s[j]的时候，dp[i][j]=max(dp[i+1][j],dp[i][j-1])
细节问题： 此时，dp表的状态转移方程需要填写的话，就必须要确保填写的时候保证dp[i+1][j],dp[i][j-1],dp[i+1][j-1]是先填写完成的。所以就必须要从二维dp表的右下角开始填写。 并且为了保证数组不越界，我们往往会在开始的时候先加上一个空格来防止越界发生，同时也要确保加上空格之后的dp表在后续填写的时候，不能有错误。但是这一题有点不一样，因为在进行数组越界之前，我们会判断是否 i= =j/i+1 == j，所以这样的话就不需要防止数组越界，直接写就行了！ 解题代码：
class Solution {
public:
int longestPalindromeSubseq(string s)
{
int n=s.size();
vector<vector<int>>dp(n,vector<int>(n));
for(int i=n-1;i>=0;i--)
{
for(int j=i;j<n;j++)
{
if(s[i]==s[j])
{
if(i==j)
dp[i][j]=1;
else if(i+1==j)
dp[i][j]=2;
else
dp[i][j]=dp[i+1][j-1]+2;
}
else
dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
}
}
return dp[0][n-1];
}
};5、分割回文串 IV(小小困难题，dp来解决)
题目链接在这里 题目解析： 给你一个字符串 s ，如果可以将它分割成三个非空回文子字符串，那么返回 true ，否则返回 false 。 其实，根据上面两个题目的我们能够判断一个字符串的从i到j位置的子串是否是回文，那这不就解决了吗。那我们先预处理一下这个字符串，然后进行两下循环就能够找到最后的结果了。 解题代码：
class Solution {
public:
bool checkPartitioning(string s)
{
int n=s.size();
vector<vector<int>>dp(n,vector<int>(n));
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;
}
}
for(int i=0;i<n-1;i++)
{
for(int j=i;j<n-1;j++)
{
if(dp[0][i]&&dp[i+1][j]&&dp[j+1][n-1])
return true;
}
}
return false;
}
};6、分割回文串 II
题目链接在这 题目解析： 目的是做到把字符串切成回文串的最少步骤。其实我刚开始看到的时候还不知道该怎么解决问题。dp表的设置？初始化？其中dp表的设计我觉得还是和之前的题目一样，二维dp表来帮助我们判断，其中dp表的含义还是和之前的题目一样，代表的是从i到j位置是否是回文串。有了这个预处理之后，我们需要做的就是找到一个解决方案，能够将这个字符串变为回文串的最少步骤。 这个时候就需要在一个dp表来表示从0到i位置到时候最少的步骤。 更多的细节看一下我的代码，相信根据上面这些题目的历练应该是能够看明白代码的。
class Solution {
public:
int minCut(string s)
{
int n=s.size();
vector<vector<bool>>dp(n,vector<bool>(n));
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;
}
}
vector<int>dpp(n,INT_MAX);
for(int i=0;i<n;i++)
{
if(dp[0][i])dpp[i]=0;
else
{
for(int j=1;j<=i;j++)
if(dp[j][i])
dpp[i]=min(dpp[i],dpp[j-1]+1);
}
}
return dpp[n-1];
}
};7、让字符串成为回文串的最少插入次数
题目链接在这 题目解析： 小小困难题，当时写的时候吓一跳呢。怎么回事呢，当时写的时候，不知道该怎么表示。 方法一： 其实有一种很简单的方法，特别的简单。就利用上面第4题最长回文子序列！注意！是最长回文子序列。找到最长回文子序列之后，用原本的整个的字符串的长度和最长子序列的长度相减一下就能够得到剩下来单着的字符串的长度，这样子也就是还需要插入的最少的次数。 方法二： 如果还是按照老方法的话，那就二维dp表，表示从i到j位置需要操作几次能够实现让字符串变为回文串。其实应该是主要能够确定下来dp表表示的是什么意思应该就能够保证题目最后的答案的正确性。 解题代码：
class Solution {
public:
int minInsertions(string s)
{
int n=s.size();
vector<vector<int>>dp(n,vector<int>(n));
for(int i=n-1;i>=0;i--)
{
for(int j=i+1;j<n;j++)
{
if(s[i]==s[j])
{
dp[i][j]=dp[i+1][j-1];
}
else
dp[i][j]=1+min(dp[i+1][j],dp[i][j-1]);
}
}
return dp[0][n-1];
}
};腾讯云开发者
