leetcode algorithm-09
本文主要对动态规划对应的例题和思路进行整理。动态规划常用于字符串匹配中,其探讨最优子状态。如何代表最优子状态,以及最优子状态之间的转移关系,就是动态规划的重点,所以在介绍思路的时候,也是就简介绍子状态是什么,如何转移。
动态规划
题1:Regular Expression Matching
思路:以$dp[i][j]$表示s字符串对应下标$i-1$和p字符串对应下标$j-1$的匹配关系。
二维数组的状态转移方程:$dp[i][j] = f(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])$,只不过在这个题中考虑的状态比较复杂和多一点而已。
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
auto match = [&](int i, int j){
if(i==0){
return false;
}
if(s[i-1] == p[j-1]||(p[j-1] == '.')){
return true;
}
return false;
};
vector<vector<int>> dp(m+1, vector<int>(n+1));
dp[0][0] = 1;
for(int i = 0 ; i <= m; i++){
for(int j = 1; j <= n; j ++){
if(match(i,j)){
dp[i][j] |= dp[i-1][j-1];
}
if(p[j-1] == '*'){
// 前面的字符出现0次,即消除前一个字符
if(j>1){
dp[i][j] |= dp[i][j-2];
}
// 前面的字符出现多次,即*复制字符进行匹配,若s[i-1]是前面的扩展即可,就要看[i-1][j]的匹配情况,如果匹配好,就可以扩展。
if(match(i,j-1)){
dp[i][j] |= dp[i-1][j];
}
}
}
}
return dp[m][n];
}
};
题2:字符串匹配: Pattern Matching LCCI
这个做法,整个思路流程非常的通畅,从特殊情况简单处理,到复杂情况复杂处理。
class Solution {
public:
int cnt[2];
bool patternMatching(string pattern, string value) {
// From simple to complex
// consider one of the Strings equals to null.
// merge all the possibilities to get a simpler form.
// note the special
if(pattern.empty()) return value.empty();
if(value.empty()){
int i = 0;
while(i < pattern.size() && pattern[i] == pattern[0]) i++;
return i == pattern.size();
}
int n = pattern.size(), m = value.size();
cnt[0] = cnt[1] = 0;
for(auto x: pattern) cnt[x-'a']++;
// if(helper(value,cnt[0]) || helper(value, cnt[1])) return true;
// 上面这个代码如果统一的话,没有截止等于0的情况,后面取余数会有问题。
if(!cnt[0]) return helper(value, cnt[1]);
else if (!cnt[1]) return helper(value, cnt[0]);
if (helper(value, cnt[1])) return true;
if (helper(value, cnt[0])) return true;
// In the following steps, a and b can not equals to null.
for(int lena = 1; lena*cnt[0] <= m - cnt[1]; lena++){
if((m-lena*cnt[0])%cnt[1] != 0) continue;
int lenb = (m-lena*cnt[0])/cnt[1];
if(check(pattern, value, lena, lenb)) return true;
}
return false;
}
bool helper(string value, int k){
// 判断是否能切分k次,且全部相等。
int m = value.size();
if(m%k != 0) return false;
int len = m/k;
for(int i = len; i < m; i+=len){
if(value.substr(i,len) != value.substr(0,len)) return false;
}
return true;
}
bool check(string pattern, string value, int lena, int lenb){
string ps[2] = {"",""}; // double quotations
// c++好像字符串不能直接相等。
// j是该模式起始的位置。
for(int i = 0, j = 0; i < pattern.size(); i++){
if(pattern[i] == 'a'){
// 如果没有被赋值,首先赋值,之后再进行比较。
if(ps[0] == "") ps[0] = value.substr(j, lena);
else if (value.substr(j,lena) != ps[0]) return false;
j += lena;
}
else{
if(ps[1] == "") ps[1] = value.substr(j, lenb);
else if (value.substr(j, lenb) != ps[1]) return false;
j += lenb;
}
}
return true;
}
};
题3:动态规划/递归转换:Unique Binary Search Trees II
思路:递归比较容易,只需要考虑主问题和次问题之间是怎么连接的,从上到下考虑即可。动态规划需要从下到上,看最优的子状态是如何形成最终的状态的,注重于状态之间的转换关系。一般情况下两者都是可以转换的。只要建立好子结构就可以。
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
# recursion,main section -> smaller section with same function.
# dynamic pogramming -> relations between consecutive states, several states -> one state.
# This is a binary search tree.
# method 1, recursion.
def helper(s, e):
# e is exclusive, s is inclusive
# return all the possibilities under the root
res = []
if s >= e:
return [None]
for i in range(s,e):
left = helper(s, i)
right = helper(i+1, e)
for l in left:
for r in right:
temp = TreeNode(i)
temp.left = l
temp.right = r
res.append(temp)
return res
if n == 0:
return None
return helper(1,n+1)
思路:在动态规划中,可以分类建立子状态的关系,这道题就是把奇数和偶数分开,奇数和偶数之间的差别,奇数之间差1,偶数之间差1,建立联系即可。
所以关键就是这里并非是连续的状态转换关系,而是差了个2.
class Solution:
def countBits(self, num: int) -> List[int]:
# 1,10,11,100,101....
dp = [0 for i in range(num+1)]
dp[0] = 0
# 找到奇偶之间的关系,奇数比之前的偶数+1,偶数比之前的num>>1的数一样的。
# 关系可以是分开创建的,即奇数和奇数建立联系,偶数和偶数建立联系。
for i in range(1,num+1):
if i%2 == 0:
dp[i] = dp[i>>1]
else:
dp[i] = dp[i>>1] + 1
return dp
题5:Stone Game
思路:是在二维 dp 的基础上使用元组分别存储两个人的博弈结果。动态规划的思路,其实本质上就是强化学习的思路,就是属于当前状态+选择过程。
tips:一般情况下,动态规划都可以写成递归,所以可以先用递归的方式想问题,找到状态之间的转移关系。
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
# 如果每次每个人都做出最优的选择,Alex还是赢,说明Alex must win the game
# 因此在该问题中,每个人的策略都是相同的,可以用一个dp数组表示。
n = len(piles)
dp = [[piles[i] if i == j else 0 for i in range(n)] for j in range(n)]
# 根据状态转移关系,为了满足从最小子状态建立的流程,需要从base的情况考虑dp数组如何遍历。
# 在下面的遍历中,i表示包含的元素个数-1,j表示起始位置,dp[s][e]中s,e表示开始的位置和最后的位置。
for i in range(1,n):
for j in range(n-i):
dp[j][j+i] = max(piles[j] - dp[j+1][j+i], piles[j+i] - dp[j][j+i-1])
return dp[0][n-1] > 0
思路:dp[i]表示以当前字符为结束的有效字符串长度(注意不是有效括号个数)。
其中这个问题有个隐藏的约束:即有效字符串的内部必须全部都是有效的括号,不可以单单出来一个字符。
总结:
还有一类问题,状态设置是以当前字符或者当前下标作为边界的状态,在这里是有效字符串的长度。
差别就是一个必须包含最后的字符作为结束字符,一个不需要包含最后的字符。
上面两种不同的状态设置方式,主要有两个差别:
-
最后做O(n)的max(dp)的运算,或者直接输出dp[-1]
-
以当前index作为边界的状态设置少了一个必须包含当前元素的约束,需要考虑多种情况.
class Solution:
def longestValidParentheses(self, s: str) -> int:
# 有效括号字符串,内部必须全部都是有效括号字符串.
dp = [0 for i in range(len(s))]
res = 0
for i in range(1,len(s)):
if s[i] == ')':
pre = i - dp[i-1] - 1
if pre >= 0 and s[pre] == '(':
dp[i] = dp[i-1] + 2
if pre > 0:
dp[i] += dp[pre-1]
res = max(res,dp[i])
return res
题7:Count Numbers with Unique Digits
思路:这里的状态选择的位数,即dp[i]代表i位数的所有情况。
有了状态的选择之后,就可以状态之间的转移方程:dp[i] = dp[i-1] + (dp[i-1]-dp[i-2])*(10-(i-1))
其中,dp[i-1]-dp[i-2]
是只考虑位数为i-1
的情况,然后和最后一位的个数相乘,是一种排列组合。
由于i
只依赖于i-1
和i-2
,所以这里可以采用节省内存的dp。
NOTE: 第一位为0不贡献位数,仍然是i-1
Summary:
动态规划其实就两个步骤:
- 状态的选择,
dp[i]
代表什么,dp[i][j]...
代表什么状态,要有代表性,可以设置多个状态数组。 - 状态的转移,不同状态之间的关系是什么,或者不同状态数组之间的转移是什么
class Solution:
def countNumbersWithUniqueDigits(self, n: int) -> int:
if n == 0:
return 1
if n == 1:
return 10
a = 1
b = 10
# b - a 是一种推导结果,只考虑i-1位的情况,最后一位的情况要看现在总共有多少位数。
# 0不贡献位数。
for i in range(2,n+1):
c = b + (b-a)*(10-(i-1))
a = b
b = c
return c
summary:动态规划的状态延续性,在某种程度上是一种承接,后一个状态可以由前一个状态修改后获得,也可以承接前一个状态,在这道题中,承接性做的好,省去了很多麻烦。
class Solution:
def isMatch(self, s: str, p: str) -> bool:
# classic dynamic programming
# is it possible to have consecutive symbol "**"??
m = len(s)
n = len(p)
dp = [[False for i in range(n+1)] for j in range(m+1)]
dp[0][0] = True
for j in range(1,n+1):
if p[j-1] == "*":
dp[0][j] = dp[0][j-1]
for i in range(1,m+1):
for j in range(1,n+1):
if (s[i-1] == p[j-1]) or p[j-1] == "?":
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == '*':
dp[i][j] = dp[i-1][j] or dp[i][j-1] # empty sequence
return dp[-1][-1]
动态规划+二分
题2:673. 最长递增子序列的个数。
题3:646. Maximum Length of Pair Chain
未分类
思路:动态规划还是最重要的两个问题:
- 状态的表示,用什么来表示一个状态,dp[i][j]表示什么意思?
- 状态的转移关系,是如何利用子状态建立起来当前状态的?
在这个题中,dp[i][j]可以表示为当前的位置为i处于j状态时的最小个数,j可以分为三个状态,即前面的红,后面的红,中间的黄,是按照顺序划分的,并不是按照种类划分的。
思路:当一个节点的状态与父节点和子节点(在数组中就是前面的状态和后面的状态会同时作用于当前的状态),该节点的状态一般有三个,其一是选择1,其二是被子节点的1影响,其三是被父节点的1影响,子节点没有作用。
贪心/动态规划:514. Freedom Trail
思路:一开始认为应该用贪心来解,但是贪心有本质上的缺点,它和动态规划的区别在于,贪心如果是正确的解,那么它每一步的解应该都能证明是最优解。如果是动态规划的话,前面的解不一定是最优解,我可以用数组来存储当前状态下的解,一步步递进求出全局最优解。
动态规划+位运算:338. Counting Bits
思路:动态规划,重要的是状态表示和转移关系,在转移关系中,除了+1,-1,+2,-2等,还有关于index的位运算,即num[i»1]和num的关系如何。