5. 最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

  • 暴力搜索,失败,耗费时间太长。
  • 动态规划,通过。

使用动态规划时首先要找到题目的状态转移方程,以字符串的长度进行增长。

方程: P(i,j) = P(i+1,j-1) && s[i]==s[j] (s是字符串)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
bool Is(string s,int st,int len)
{
for(int i=0;i<len/2;i++)
{
if(s[st+i]!=s[st+len-i-1])
return false;
}
return true;
}
string longestPalindrome(string s) {
int len = s.length();
int max=-1;
string res;
vector<vector<bool>> dp(len,vector<bool>(len));
for(int l=0;l<len;l++)
{
for(int i=0;i+l<len;i++)
{
if(l==0)
{
dp[i][i+l]=true;
}
else if(l==1)
{
dp[i][i+l]= s[i]==s[i+l];
}
else
{
dp[i][i+l] = dp[i+1][i+l-1] && s[i]==s[i+l];
}
if(dp[i][i+l] &&l>max)
{
max=l;
res=s.substr(i,max+1);
}
}
}
return res;
}
};

32. 最长有效括号

动态规划算法。

1

  • dp[i][j] = n ,代表从i - j 是有效括号字符串 且长度为n。
  • 列出状态转移方程:
    dp[i][j] =
    • if dp[i+1][j-1]>0 && s[i]==’ ( ’ && s[j] ==’ ) ’ then dp[i][j] = dp[i+1][j-1]+2
    • for k = i+1 : j-1
      if s[i][k]>0 && s[k+1][j]>0 then dp[i][j] = dp[i][k]+dp[i+1][j]
  • 编写算法,发现时间复杂度有点高,最后有三个用例时间超时。
  • 总结: 可以发现 n=j-i+1,这就说明,j在此处有些多余,改进时可将j去掉。

2

  • dp[i]=n , 代表截至到 i 的有效括号字符串长度是 n 。
  • 状态转移方程:
    dp[i] = if s[i]==’)’
    • if s[i-1] == ‘(’ then dp[i] = dp[i-2] + 2
    • else if s[i - dict[i-1]-1]==’(’ then dp[i] = dp[i-1] + 2 + dp[i - dict[i-1]-2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int longestValidParentheses(string s) {
int len = s.length();
vector<int> dict(len,0);
int max = 0;
for(int i=1;i<len;i++)
{
if(s[i]==')')
{
if(s[i-1]=='(')
{
dict[i] = i>1?dict[i-2]+2:2;
}
else if(i - dict[i-1]-1>=0 &&s[i - dict[i-1]-1]=='(')
{
dict[i] = dict[i-1]+2;
if(i - dict[i-1]-2>=0 &&dict[i - dict[i-1]-2]>0)
{
dict[i]+=dict[i - dict[i-1]-2];
}
}
max = dict[i]>max?dict[i]:max;
}
}
return max;
}
};

62. 不同路径

  • 方程:dp[i][j]=dp[i1][j]+dp[i][j1]dp[i][j] = dp[i-1][j] + dp[i][j-1]

  • 注意,对于第一行 dp[0][j],或者第一列 dp[i][0],由于都是在边界,所以只能为 1 !!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int uniquePaths(int m, int n) {
int *dp = (int *)malloc(sizeof(int)*m*n);
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i==0||j==0)
{
dp[i*n+j] =1;
}
else
{
dp[i*n+j] =dp[i*n+j-n]+dp[i*n+j-1] ;
}
}
}
return dp[m*n-1];
}
};

数学方法: 机器人会走 m-1 + n-1 步,其中一定需要向下走 m-1 步,所以有 Cm+n2m1C_{m+n-2} ^ {m-1}

64. 最小路径和

  • 类似于62题,唯一的区别就是对于路径增加了权重,从而无法使用数学方法解答了。

  • 方程:dp[i][j]=min(dp[i1][j],dp[i][j1])+grid[i][j]dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m,vector<int>(n));

for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i==0&&j==0)
{
dp[i][j] = grid[i][j];
}
else if(i==0)
{
dp[i][j]=dp[i][j-1]+grid[i][j];
}
else if(j==0)
{
dp[i][j]=dp[i-1][j]+grid[i][j];
}
else
{
dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
}
return dp[m-1][n-1];

}
};

121. 买卖股票的最佳时机

  • 方程:dp[i]=max(dp[j]+price[i]price[j])(j=i1:0)dp[i] = max(dp[j] + price[i] - price[j]) (j = i-1 : 0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len =prices.size();
vector<int> dp(len,0);
int max = 0;
for(int i=1;i<len;i++)
{
for(int j=i-1;j>=0;j--)
{
if(prices[i]>=prices[j])
{
dp[i] = dp[j] +prices[i]-prices[j];
break;
}
}
max = max<dp[i]?dp[i]:max;
}
return max;

}
};

198. 打家劫舍

  • 方程 dp[i]=max(dp[i1],dp[i2]+nums[i]);dp[i] = max(dp[i-1],dp[i-2]+nums[i]);
  • 本题目中我们不需要全部放的dp数组,所以还可以进行空间优化,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int rob(vector<int>& nums) {
int size = nums.size();
if(size==0)
return 0;
if(size==1)
return nums[0];
vector<int> dp(size,0);
dp[0] = nums[0];
dp[1] = max(nums[0],nums[1]);
for(int i=2;i<size;i++)
{
dp[i] = max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[size-1];
}
};

338. 比特位计数

  • 主要的是需要找到状态转移函数,其他的就好办了,可以通过观察i分别和 i-1,i/2的关系来找到方程。
  • dp[i]={dp[i1]+1,ifimod20dp[i/2],ifimod2=0dp[i]=\begin{cases} dp[i-1] + 1,&{if}&{i \bmod 2} \not={0}\\ dp[i/2],&{if}&{i \bmod 2}={0} \end{cases}
  • 对上述方程还可以进行进一步优化, dp[i]=dp[i/2]+imod2dp[i] = dp[i/2] + i\bmod2
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
vector<int> countBits(int num) {
vector<int> ret(num+1,0);
for(int i=0;i<=num;i++)
{
ret[i] = i&1? ret[i-1]+1:ret[i/2];
}
return ret;
}
};

96. 不同的二叉搜索树

  • 主要还是要找到状态转移函数。
  • 思路是将一个大的树分为两个小的树分别计算,然后左右两边相乘在求和。如n的节点的树,以第1个节点为根节点,分成左边0个节点,右边n-1节点的树,以第2个节点为根节点,分成左边1个节点,右边n-2节点的树,以第3个节点为根节点,分成左边2个节点,右边n-3节点的树。
  • dp[i]=j=0i1dp[j]dp[i1j]dp[i] = \displaystyle\sum_{j=0}^{i-1} dp[j]*dp[i-1-j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n+1,1);
for(int i=1;i<=n;i++)
{
int sum=0;
for(int j=0;j<i;j++)
{
sum+=dp[j]*dp[i-1-j];
}
dp[i] = sum;
}
return dp[n];
}
};