动态规划-题型二

全文参考：
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 分。

我们想求的答案是先手和后手最终分数之差，按照这个定义也就是 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

对于这个问题的每个状态，可以做的选择有两个：选择最左边的那堆石头，或者选择最右边的那堆石头。 我们可以这样穷举所有状态：

n = piles.length
for 0 <= i < n:
	for j <= i < n:
		for who in {fir, sec}:
			dp[i][j][who] = max(left, right)

上面的伪码是动态规划的一个大致的框架，股票系列问题中也有类似的伪码。这道题的难点在于，两人是交替进行选择的，也就是说先手的选择会对后手有影响，这怎么表达出来呢？（还得知道最优子结构）
根据我们对 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]
# 此时轮到我，我变成了先手。

根据 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

代码
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;
    }

动态规划之正则表达 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;
}

然后，我稍微改造一下上面的代码，略微复杂了一点，但意思还是一样的，很容易理解吧：

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();
}

如上改写，是为了将这个算法改造成递归算法（伪码）：

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:])

二、处理点号「.」通配符
点号可以匹配任意一个字符，万金油嘛，其实是最简单的，稍加改造即可：

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:])

三、处理*通配符
星号通配符可以让前一个字符重复任意次数，包括零次。那到底是重复几次呢？这似乎有点困难，不过不要着急，我们起码可以把框架的搭建再进一步：

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:])

星号前面的那个字符到底要重复几次呢？这需要计算机暴力穷举来算，假设重复 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

本文地址：https://blog.csdn.net/ryontang/article/details/107894171