0%

leetcode动态规划专题

感觉dp真的很困难,刷不动。打算后面几天刷一下dp的题。

leetcode 5 最长回文子串:

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

1
2
3
4
5
6
7
示例 1
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2
输入: “cbbd”
输出: “bb”

思路:参考了算法笔记的最长回文子串的做法,时间复杂度为\(O(N^2)\)。令dp[i][j]表示s[i]到s[j]所表示的子串是否时回文子串,是则为1,不是为0。这样根据s[i]是否等于s[j],就可以把转移情况分为两类:
s[i]==s[[j],那么只要s[i+1][j-1]是回文子串,s[i]至s[j]就是回文子串;如果s[i+1][j-1]不是回文子串,则s[i]至s[j]也不是回文子串。
s[i]!=s[j],那么s[i]至s[j]一定不是回文子串。
由此可以写出状态转移方程:
\(
dp[i][j] =
\begin{cases}
dp[i+1][j-1], & \text{s[i]==s[j]} \\
0, & \text{s[i]!=s[j]}
\end{cases}
\)
边界:\(dp[i][i]=1,dp[i][i+1]=(s[i]==s[i+1])?1:0\)。
到这里还有一个问题没有解决,那就是如果按照i和j从小到大的顺序来枚举子串的两个端点,然后更新dp[i][j],会无法保证dp[i+1][j-1]已经被计算过,从而无法得到正确的dp[i][j]。
如图所示,先固定i==0,然后枚举j从2开始。当求解dp[0][2]时,将会转换为求dp[1][1],而dp[1][1]时在初试化中得来得,当求解dp[0][3]时,将会转换为dp[1][2],而dp[1][2]也是在初始化中得来的,当求解dp[0][4]时,将会转换为dp[1][3],但是dp[1][3]并不是已经计算过的值,因此无法状态转移。事实上,无论对i和j的枚举顺序作何调整,都无法调和这个矛盾,因此必须想办法寻找新的枚举方式。
根据递推写法从边界出发的原理,注意到边界表示的是长度为1和2的子串,且每次转移时都对子串的长度减了1,因此不妨考虑按子串的初始位置进行枚举,即第一遍将长度为3的子串的dp值全部求出,第二遍通过第一遍结果计算出长度为4的子串的dp值…这样就可以避免状态无法转移的问题。可以先枚举子串长度L,再枚举左端点i,这样右端点i+L-1也可以直接得到。

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
class Solution {
public:
int dp[1010][1010];
string longestPalindrome(string s) {
string res = "";
int n = s.length(),ans=1,temp=0;
for(int i=0;i<n;i++){
dp[i][i]=1;
if(i<n-1){
if(s[i]==s[i+1]){
dp[i][i+1]=1;
ans = 2;
temp = i;
}
}
}
for(int L = 3;L<=n;L++){
for(int i=0;i+L-1<n;i++){
int j=i+L-1;
if(s[i]==s[j]&&dp[i+1][j-1]==1){
dp[i][j]=1;
temp = i;
ans = L;
}
}
}
int m = temp + ans;
for(int i=temp;i<m;i++)res+=s[i];
return res;
}
};

leetcode 647 回文子串

给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被计为是不同的子串。
示例 1:
输入: “abc”
输出: 3
解释: 三个回文子串: “a”, “b”, “c”.
示例 2:
输入: “aaa”
输出: 6
说明: 6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”.
注意:
输入的字符串长度不会超过1000。

思路:上面的代码稍加修改即可解。

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
class Solution {
public:
int dp[1010][1010];
int countSubstrings(string s) {
int n = s.length(),result=n;
for(int i=0;i<n;i++){
dp[i][i]=1;
if(i<n-1){
if(s[i]==s[i+1]){
dp[i][i+1]=1;
result++;
}
}
}
for(int L = 3;L<=n;L++){
for(int i=0;i+L-1<n;i++){
int j=i+L-1;
if(s[i]==s[j]&&dp[i+1][j-1]==1){
dp[i][j]=1;
result++;
}
}
}
return result;
}
};

leetcod 1025 除数博弈

爱丽丝和鲍勃一起玩游戏,他们轮流行动。爱丽丝先手开局。最初,黑板上有一个数字N 。在每个玩家的回合,玩家需要执行以下操作:
选出任一x,满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作,就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True,否则返回 false。假设两个玩家都以最佳状态参与游戏。
示例 1:
输入:2
输出:true
解释:爱丽丝选择 1,鲍勃无法进行操作。
示例 2:
输入:3
输出:false
解释:爱丽丝选择 1,鲍勃也选择 1,然后爱丽丝无法进行操作。
提示:
1 <= N <= 1000

思路:有一种取巧找规律的做法很简单就不说了,自己推一下就行了。说一下自己的动态规划做法。首先明确一点,就是对于每个数其胜负结果都是确定的,也就是说每一个必胜态都有一个必败态的转化,每个必败态都有一个必胜态的转化。举个栗子:用dp数组来记录每个N的胜负情况,显然dp[1]=0,dp[2]=1,dp[3]=0,我们可以有前面状态的dp[i]来递推出后面dp[i+1]。求解dp[4]时,我们判断从dp[1-3]中可以被4整除数中是否有一个使得N-x必败态的数,如果有,则dp[4]则为必胜态,因为先手选数的玩家选了那个数后,使得对面到了必败态。例如我们可以选的数有1,2,选后的状态为dp[3]=0,dp[2]=1,所以我们肯定要选1使得对方转到必败态。代码实现也很简单:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
bool dp[1010];
bool divisorGame(int N) {
int temp;
dp[1]=0,dp[2]=1,dp[3]=0;
for(int i=4;i<=N;i++){
for(int j=1;j<N-1;j++){
if(i%j==0){
if(dp[i-j]==0)dp[i]=1;
break;
}
}
}
return dp[N];
}
};

leetcode 303 区域和检索

给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。
示例:
给定 nums = [-2, 0, 3, -5, 2, -1],求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明:
你可以假设数组不可变。
会多次调用 sumRange 方法。

思路:水题,直接前缀和完事。

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
43
44
45
46
47
48
49
50
51
52
53
class NumArray{
public:
vector<int>dp,num;
int n;
NumArray(vector<int>& nums)
{
n = nums.size();
num = nums;
presum();
}

int sumRange(int i, int j)
{
return dp[j]-dp[i]+num[i];
}
void presum()
{
if(n)
{
dp.push_back(num[0]);
for(int i=1; i<n; i++)
{
dp.push_back(dp[i-1]+num[i]);
}
}
}
};class NumArray{
public:
vector<int>dp,num;
int n;
NumArray(vector<int>& nums)
{
n = nums.size();
num = nums;
presum();
}

int sumRange(int i, int j)
{
return dp[j]-dp[i]+num[i];
}
void presum()
{
if(n)
{
dp.push_back(num[0]);
for(int i=1; i<n; i++)
{
dp.push_back(dp[i-1]+num[i]);
}
}
}
};