5. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
- 暴力搜索，失败，耗费时间太长。
- 动态规划，通过。
使用动态规划时首先要找到题目的状态转移方程，以字符串的长度进行增长。
方程： P(i,j) = P(i+1,j-1) && s[i]==s[j] (s是字符串)
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]
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[i-1][j] + dp[i][j-1]$
-
注意，对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为 1 ！！！
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 步，所以有 $C_{m+n-2} ^ $
64. 最小路径和
-
类似于62题，唯一的区别就是对于路径增加了权重，从而无法使用数学方法解答了。
-
方程：$dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]$
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 = i-1 : 0)$
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;
}
};
- $dp[i]=max(dp[i-1],prices[i]-min)$
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()==0)
return 0;
vector<int> dp(prices.size(),0);
int _min = prices[0];
for(int i=1;i<prices.size();i++)
{
dp[i] = max(dp[i-1],prices[i]-_min);
_min = min(_min,prices[i]);
}
return dp[prices.size()-1];
}
};
198. 打家劫舍
- 方程 $dp[i] = max(dp[i-1],dp[i-2]+nums[i]);$
- 本题目中我们不需要全部放的dp数组，所以还可以进行空间优化，
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]=\begin
dp[i-1] + 1,&&{i \bmod 2} \not={0}\
dp[i/2],&&{i \bmod 2}={0}
\end$ - 对上述方程还可以进行进一步优化， $dp[i] = dp[i/2] + i\bmod2$
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] = \displaystyle\sum_^ dp[j]*dp[i-1-j]$
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];
}
};
279. 完全平方数
- 动态规划 $dp[i] = min(dp[i-k]+1) , k\in sq$ (sq为平方数的序列)
class Solution {
public:
int numSquares(int n) {
vector<int> sq;
vector<int> dp(n+1);
for (int i = 1; i * i <= n; i++)
{
sq.push_back(i * i);
}
for (int i = 1; i < n + 1; i++)
{
int _min = i;
for (int j = 0; j < sq.size() && i - sq[j] >= 0; j++)
{
_min = min(_min, dp[i - sq[j]] + 1);
}
dp[i] = _min;
}
return dp[n];
}
};
309. 最佳买卖股票时机含冷冻期
- $dp[i] = max{dp[j]+max{prices[i]-prices[k](k= j+2 \backsim i-1)}}(j= 0 \backsim i-1)$ 时间复杂度$O(n^2)$
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()<2)
return 0;
vector<int> dp(prices.size());
int m1=prices[0];
m1 = min(m1,prices[1]);
if(prices.size()>2)
m1 = min(m1,prices[2]);
dp[1] = max(0,prices[1]-prices[0]);
for(int i=2;i<prices.size();i++)
{
int m = prices[i];
for(int j=i-2;j>0;j--)
{
m = min(m,prices[j+2]);
dp[i]= max(dp[i],(dp[j]+prices[i]-m));
}
dp[i]= max(dp[i],dp[i-1]);
dp[i]= max(dp[i],prices[i]-m1);
}
return dp[prices.size()-1];
}
};
- 另外一种，带有三种状态转换的动态规划，时间复杂度O(n)。见解析