动态规划-题型二_dp数组
赞
踩
全文参考：
labuladong
动态规划之博弈问题877.石子游戏
解决博弈问题的动态规划通用思路
本文就借石头游戏来讲讲「假设两个人都足够聪明，最后谁会获胜」这一类问题该如何用动态规划算法解决。
博弈类问题的套路都差不多，下文举例讲解，其核心思路是在二维 dp 的基础上使用元组分别存储两个人的博弈结果。掌握了这个技巧以后，别人再问你什么俩海盗分宝石，俩人拿***的问题，你就告诉别人：我懒得想，直接给你写个算法算一下得了。
我们石头游戏改的更具有一般性：
你和你的朋友面前有一排石头堆，用一个数组 piles 表示，piles[i] 表示第 i 堆石子有多少个。你们轮流拿石头，一次拿一堆，但是只能拿走最左边或者最右边的石头堆。所有石头被拿完后，谁拥有的石头多，谁获胜。
石头的堆数可以是任意正整数，石头的总数也可以是任意正整数，这样就能打破先手必胜的局面了。比如有三堆石头 piles = [1, 100, 3]，先手不管拿 1 还是 3，能够决定胜负的 100 都会被后手拿走，后手会获胜。
假设两人都很聪明，请你设计一个算法，返回先手和后手的最后得分（石头总数）之差。比如上面那个例子，先手能获得 4 分，后手会获得 100 分，你的算法应该返回 -96。
这样推广之后，这个问题算是一道 Hard 的动态规划问题了。博弈问题的难点在于，两个人要轮流进行选择，而且都贼精明，应该如何编程表示这个过程呢？
一、定义dp数组的含义
介绍 dp 数组的含义之前，我们先看一下 dp 数组最终的样子：
下文讲解时，认为元组是包含 first 和 second 属性的一个类，而且为了节省篇幅，将这两个属性简写为 fir 和 sec。比如按上图的数据，我们说 dp[1][3].fir = 10，dp[0][1].sec = 3
以下是对dp数组含义的解释：
dp[i][j].fir 表示，对于piles[i...j] 这部分石头堆，先手能获得的最高分数
dp[i][j].sec 表示，对于piles[i...j]这部分石头堆，后手能获得的最高分数
举例理解一下，假设 piles = [3, 9, 1, 2]，索引从 0 开始
dp[0][1].fir = 9 意味着：面对石头堆 [3, 9]，先手最终能够获得 9 分。
dp[1][3].sec = 2 意味着：面对石头堆 [9, 1, 2]，后手最终能够获得 2 分。
- 1
- 2
- 3
- 4
- 5
- 6
我们想求的答案是先手和后手最终分数之差，按照这个定义也就是 dp[0][n-1].fir - dp[0][n-1].sec，即面对整个 piles，先手的最优得分和后手的最优得分之差。
二、状态转移方程
状态转移方程很简单，首先要找到所有「状态」和每个状态可以做的「选择」，然后择优。
根据前面对 dp 数组的定义，状态显然有三个：开始的索引 i，结束的索引 j，当前轮到的人。
dp[i][j][fir or sec]
其中：
0<=i<piles.length
i<=j<piles.length
- 1
- 2
- 3
- 4
- 5
对于这个问题的每个状态，可以做的选择有两个：选择最左边的那堆石头，或者选择最右边的那堆石头。 我们可以这样穷举所有状态：
n = piles.length
for 0 <= i < n:
for j <= i < n:
for who in {fir, sec}:
dp[i][j][who] = max(left, right)
- 1
- 2
- 3
- 4
- 5
上面的伪码是动态规划的一个大致的框架，股票系列问题中也有类似的伪码。这道题的难点在于，两人是交替进行选择的，也就是说先手的选择会对后手有影响，这怎么表达出来呢？（还得知道最优子结构）
根据我们对 dp 数组的定义，很容易解决这个难点，写出状态转移方程：
dp[i][j].fir=max(piles[i]+dp[i+1][j].sec, piles[j]+ dp[i][j-1].sec) dp[i][j].fir=max(选择最左边的石头堆，选择最右边的石头堆) # 解释：我作为先手，面对 piles[i...j] 时，有两种选择： # 要么我选择最左边的那一堆石头，然后面对 piles[i+1...j] # 但是此时轮到对方，相当于我变成了后手； # 要么我选择最右边的那一堆石头，然后面对 piles[i...j-1] # 但是此时轮到对方，相当于我变成了后手。 # 我作为后手 if 先手选择左边: dp[i][j].sec=dp[i+1][j].fir if 先手选择右边: dp[i][j].sec=dp[i][j-1].fir # 解释：我作为后手，要等先手先选择，有两种情况： # 如果先手选择了最左边那堆，给我剩下了 piles[i+1...j] # 此时轮到我，我变成了先手； # 如果先手选择了最右边那堆，给我剩下了 piles[i...j-1] # 此时轮到我，我变成了先手。
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
根据 dp 数组的定义，我们也可以找出 base case，也就是最简单的情况：
dp[i][j].fir=piles[i]
dp[i][j].sec=0
其中0<=i==j<n
# 解释：i 和 j 相等就是说面前只有一堆石头 piles[i]
# 那么显然先手的得分为 piles[i]
# 后手没有石头拿了，得分为 0
- 1
- 2
- 3
- 4
- 5
- 6
代码
labuladong
bool stoneGame(vector<int>& piles) { int n = piles.size(); std::pair<int, int> pair(0, 0); vector<std::pair<int, int>> temp(n, pair); // 初始化 dp 数组 vector<vector<std::pair<int, int>>> dp(n, temp); // base case for(int i = 0; i<n; i++){ dp[i][i].first = piles[i]; dp[i][i].second = 0; } // 状态转移方程 // 从倒数第二行横着遍历就可以啦 for(int i = n-2; i>=0; i--){ for(int j = i+1; j<n; j++){ int choose_left = piles[i]+dp[i+1][j].second; int choose_right = piles[j]+dp[i][j-1].second; // [i,j]的石头，比较两端 if(choose_left>=choose_right){ // 左边大，先手取左边 dp[i][j].first=choose_left; // 如果先手选择了最左边那堆，给我剩下了 piles[i+1...j] // 此时轮到我，我变成了先手 dp[i][j].second=dp[i+1][j].first; } else { // 同理，右边大，先手取右边 dp[i][j].first=choose_right; // dp[i][j].second=dp[i][j-1].first; } } } return dp[0][n-1].first>dp[0][n-1].second; }
- 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
动态规划之正则表达 10.正则表达式匹配
labuladong
一、热身
第一步，我们暂时不管正则符号，如果是两个普通的字符串进行比较，如何进行匹配？我想这个算法应该谁都会写：
bool isMatch(string text, string pattern){
if(text.size()!=pattern.size()) return false;
for(int j =0; j<pattern.size(); j++){
if(pattern[j]!=text[j])
return false;
}
return true;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
然后，我稍微改造一下上面的代码，略微复杂了一点，但意思还是一样的，很容易理解吧：
bool isMatch(string text, string pattern){
int i = 0; // text 的索引位置
int j = 0; // pattern 的索引位置
while(j<pattern.size()){
if(i>=text.size()){
return false;
}
if(pattern[j++]!=text[i++])
return false;
}
// 相等则说明完成匹配
return j == text.size();
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
如上改写，是为了将这个算法改造成递归算法（伪码）：
def isMatch(text, pattern)->bool:
if pattern is empty: return (text is empty?)
first_match = (text not empty) and pattern[0] == text[0]
return first_match and isMatch(text[1:], pattern[1:])
- 1
- 2
- 3
- 4
二、处理点号「.」通配符
点号可以匹配任意一个字符，万金油嘛，其实是最简单的，稍加改造即可：
def isMatch(text, pattern)->bool:
if not pattern: return not text
first_match = bool(text) and pattern[0] in {text[0], '.'}
return first_match and isMatch(text[1:], pattern[1:])
- 1
- 2
- 3
- 4
三、处理*通配符
星号通配符可以让前一个字符重复任意次数，包括零次。那到底是重复几次呢？这似乎有点困难，不过不要着急，我们起码可以把框架的搭建再进一步：
def isMatch(text, pattern)->bool:
if not pattern: return not text
first_match = bool(text) and pattern[0] in {text[0], '.'}
if len(pattern)>=2 and pattern[1]=='*':
# 发现'*'通配符
else:
return first_match and isMatch(text[1:], pattern[1:])
- 1
- 2
- 3
- 4
- 5
- 6
- 7
星号前面的那个字符到底要重复几次呢？这需要计算机暴力穷举来算，假设重复 N 次吧。前文多次强调过，写递归的技巧是管好当下，之后的事抛给递归。具体到这里，不管 N 是多少，当前的选择只有两个：匹配 0 次、匹配 1 次(有无匹配的问题)。所以可以这样处理：
if len(pattern) >= 2 and pattern[1] == '*':
return isMatch(text, pattern[2:]) or first_match and isMatch(text[1:], pattern)
# 解释：如果发现有字符和 '*' 结合，
# 或者匹配该字符 0 次，然后跳过该字符和 '*'
# 或者当 pattern[0] 和 text[0] 匹配后，移动 text
- 1
- 2
- 3
- 4
- 5
思路二：官方题解
1.思路：
字符匹配想到逐步匹配，缩小范围的过程：
每次从字符串 p 中取出一个字符或者「字符 + 星号」的组合，并在 s中进行匹配
对于 pp 中一个字符而言，它只能在 ss 中匹配一个字符，匹配的方法具有唯一性；而对于 p中字符 + 星号的组合而言，它可以在 s中匹配任意自然数个字符，并不具有唯一性。因此我们可以考虑使用动态规划，对匹配的方案进行枚举。
2.选择和状态
选择s[j]中的第j个字母进行匹配
定义dp[i][j]: 表示p的前i个字符与s的前j个字符是否能够匹配
3.状态转移
a.base case
dp[0][0]代表都是空字符=true;
dp[0][1:j]=F
dp[1:i][0]=F (except 若p[2]=, 则dp[1][0]=ture，即第二个发挥作用:0个前向字母，抵消第一个字母p[1], 则p第一个位置也为空字符)
b.状态转移方程
以一个例子详解动态规划转移方程：
S = abbbbc
P = abdc
(1)当 i, j 指向的字符均为字母（或 ‘.’ 可以看成一个特殊的字母）时，
只需判断对应位置的字符即可，
若相等，只需判断 i,j 之前的字符串是否匹配即可，转化为子问题 f[i-1][j-1].
若不等，则当前的 i,j 肯定不能匹配，为 false.
(2)当前 j 指向的字符为星号：
图一：
图二：
官方题解地址
视频地址
动态规划之四键键盘
一、选择和状态
选择：还是那 4 个，A、C-A、C-C、C-V
状态：需要知道什么信息才能将原问题分解为规模更小的子问题
状态只定义一个：剩余的敲击次数n
这个算法基于一个这样的事实，最优按键序列一定只有两种情况：
要么一直按A：A,A,A,…,A（当N比较小时）
要么是这么一个形式：A,A,…C-A,C-C,C-V,…CV（当N比较大时）
.
因为字符数量少（N 比较小）时，C-A C-C C-V 这一套操作的代价相对比较高，可能不如一个个按 A；而当 N 比较大时，后期 C-V 的收获肯定很大。这种情况下整个操作序列大致是：开头连按几个 A，然后 C-A C-C 组合再接若干 C-V，然后再 C-A C-C 接着若干 C-V，循环下去。
二、定义dp
定义：dp[i] 表示 i 次操作后最多能显示多少个 A
换句话说，最好一次按键要么是A要么是C-V, 明确了这一点，可以通过这两种情况来设计算法：
int[] dp = new int[N+1]
// 定义：dp[i] 表示 i 次操作后最多能显示多少个 A
for(int i = 0; i<=N; i++){
dp[i]=max(
这次按A键，
这次按C-V
)
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
对于「按 A 键」这种情况，就是状态 i - 1 的屏幕上新增了一个 A 而已，很容易得到结果：
dp[i]=dp[i-1]+1;
- 1
但是，如果要按 C-V，还要考虑之前是在哪里 C-A C-C 的
刚才说了，最优的操作序列一定是 C-A C-C 接着若干 C-V，所以我们用一个变量 j 作为若干 C-V 的起点。那么 j 之前的 2 个操作就应该是 C-A C-C 了：
public int maxA(int N){ int[] dp = new int[N+1]; // base case dp[0]=0; for(int i =1; i<=N; i++){ // 按A键 dp[i]=dp[i-1]+1; // 寻找一个最佳的j点，j从2就可以开始一直cv了 for(int j =2; j<i; j++){ // 全选 & 复制 dp[j-2]，连续粘贴 i - j 次 // 屏幕上共 dp[j - 2] * (i - j + 1) 个 A // 比较在dp[i]处按A, 还是在dp[i-2]处开始c-a c-v, 到dp[i]这一行为c-v的总个数 dp[i]=Math.max(dp[i], dp[j-2]*(i-j+1)); } } // N 次按键之后最多有几个 A？ return dp[N]; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
动态规划之KMP字符匹配算法
kmp算法的实现(正月点灯笼)
# include<stdio.h>
void prefix_table(char pattern[], int prefix[], int n){
prefix[0]=0;
int len = 0;
int i;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
labuladong
一、KMP 算法概述
public class KMP{
private int[][] dp;
private String pat;
public KMP(String pat){
this.pat = pat;
// 通过pat构建dp数组
// 需要O(M)时间
}
public int search(String txt){
// 借助dp数组去匹配txt
// 需要O(N)时间
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
二、状态机概述
为什么说 KMP 算法和状态机有关呢？是这样的，我们可以认为 pat 的匹配就是状态的转移。比如当 pat = “ABABC”：
pat的不同状态上图都说明了；(目前在哪个状态说明pat已经在txt中匹配到哪个状态了，如果遇到txt下一个字母，则会发现相应的状态转移，即转移后pat的状态去匹配txt当前的字母)
圆圈内的数字就是状态，状态 0 是起始状态，状态 5（pat.length）是终止状态。开始匹配时 pat 处于起始状态，一旦转移到终止状态，就说明在 txt 中找到了 pat。比如说当前处于状态 2，就说明字符 “AB” 被匹配：
另外，处于不同状态时，pat 状态转移的行为也不同。比如说假设现在匹配到了状态 4，如果遇到字符 A(text中的字符A) 就应该转移到状态 3，遇到字符 C 就应该转移到状态 5，如果遇到字符 B 就应该转移到状态 0：
- 这个状态转移的匹配过程就是KMP算法的核心逻辑
为了描述状态转移图，我们定义一个二维dp数组，它的含义如下：
dp[j][c]=next定义如下：当前状态j,遇到字符c的下一个状态是？
见图片
dp[j][c] = next
0<= j < M, 代表当前的状态
0 <= c < 256, 代表遇到的字符(ASCII码)
0 <= next <= M, 代表下一个状态
dp[1]['B'] = 2表示
当前是状态1，如果遇到字符B，
pat应该转移到状态2
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
根据我们这个 dp 数组的定义和刚才状态转移的过程，我们可以先写出 KMP 算法的 search 函数代码：
public int search(String txt){ int M = pat.length(); int N = txt.length(); // pat的初始态为0 int j = 0; for(int i = 0; i<N; i++){ // 当前是状态j, 遇到字符txt[i] // pat应该转移到哪个状态 j = dp[j][txt.charAt(i)]; // 如果达到终止态，返回匹配开头的索引 if(j==M) return i-M+1; } //没有到达终止态，匹配失败 return -1; } # 如何通过 pat 构建这个 dp 数组？
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
三、构建状态转移图
回想刚才说的：要确定状态转移的行为，必须明确两个变量，一个是当前的匹配状态，另一个是遇到的字符，而且我们已经根据这个逻辑确定了 dp 数组的含义，那么构造 dp 数组的框架就是这样：
for 0<= j < M: # 状态
for 0<= c < 256: # 字符
dp[j][c] = next
- 1
- 2
- 3
这个next状态应该怎么求呢？如果遇到的字符 c 和 pat[j] 匹配的话，状态就应该向前推进一个，也就是说next=j+1, 我们不妨称这种情况为状态推进：
中间省略了一大堆
这样，我们就细化一下刚才的框架代码：
int X # 影子状态
for 0<=j<M:
for 0<=c < 256:
if c==pat[j]:
#状态推进
dp[j][c]=j+1
else:
#状态重启
#委托X计算重启位置
dp[j][c]=dp[X][c] # 再由X去做转移
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
四、代码实现
如果之前的内容你都能理解，恭喜你，现在就剩下一个问题：影子状态 X 是如何得到的呢？下面先直接看完整代码吧。
public class KMP{ private int[][] dp; private String pat; public KMP(String pat){ this.pat = pat; int M = pat.length(); // dp[状态][字符] = 下个状态 dp = new int[M][256] // base case dp[0][pat.charAt(0)] = 1; # 只有遇到 pat[0] 这个字符才能使状态从 0 转移到 1，遇到其它字符的话还是停留在状态 0 // 影子状态x初始为0 int X = 0; // 当前状态j从1开始 for(int j = 1; j<M; j++){ for(int c = 0; c<256; c++){ if(pat.charAt(j)==c) dp[j][c]=j+1; else dp[j][c]=dp[X][c] } // 更新影子状态 X = dp[X][pat.charAt(j)]; } } public int search(String txt){...} }
- 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
关于影子状态的更新：
影子状态 X 是先初始化为 0，然后随着 j 的前进而不断更新的。下面看看到底应该如何更新影子状态 X：
int X = 0; for (int j = 1; j < M; j++) { ... // 更新影子状态 // for(int c = 0; c<256;c++) // 当前是状态 X，遇到字符 pat[j]， // pat 应该转移到哪个状态？ X = dp[X][pat.charAt(j)]; } # 更新 X 其实和 search 函数中更新状态 j 的过程是非常相似的： int j = 0; for (int i = 0; i < N; i++) { // 当前是状态 j，遇到字符 txt[i]， // pat 应该转移到哪个状态？ j = dp[j][txt.charAt(i)]; ... } # 注意代码中 for 循环的变量初始值，可以这样理解：后者即search函数中更新状态j,是在 txt 中匹配 pat # 前者即，影子状态X, 是在 pat 中匹配 pat[1..end] # 状态 X 总是落后状态 j 一个状态，与 j 具有最长的相同前缀 # 把 X 比喻为影子状态，似乎也有一点贴切 public class KMP{ private int[][] dp; private String pat; public KMP(String pat){ this.pat = pat; int M = pat.length(); // dp[状态][字符] = 下个状态 dp = new int[M][256]; // base case dp[0][pat.charAt(0)] = 1; // 影子状态 X 初始为 0 int X = 0; // 构建状态转移图（稍改的更紧凑了） for (int j = 1; j < M; j++){ for (int c = 0; c < 256; c++){ // 状态转移方程 if(pat.charAt(j)==c) dp[j][c]=j+1; else // 回退到影子状态 dp[j][c]=dp[X][c] } // 影子状态就是匹配Pat,M++,影子状态也要更新 // 更新影子状态 X = dp[X][pat.charAt(j)]; } } public int search(String txt){ int M = pat.length(); int N = txt.length(); // pat 的初始态为 0 int j = 0; for (int i = 0; i < N; i++) { // 计算 pat 的下一个状态 // dp已经初始化好了，已经有影子状态的值存储了，直接拿过来搜 j = dp[j][txt.charAt(i)]; // 到达终止态，返回结果 if (j == M) return i - M + 1; } // 没到达终止态，匹配失败 return -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
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
int M = pat.length;
int N = txt.length;
- 1
- 2
- 3
- 4
