知识点

知识点
1. 博弈类问题：
  1. 博弈类问题，一般都是「假设两个人都足够聪明，最后谁会获胜」这一类问题。其核心思路是在二维 dp 的基础上使用元组分别存储两个人的博弈结果，这些问题一般都有相似的解题思路。类似的博弈问题有：海盗分金问题，石头游戏问题等等。
  2. 经典实例：石头问题
    1. 题目描述
      
      你和你的朋友面前有一排石头堆，用一个数组 piles 表示，piles[i] 表示第 i 堆石子有多少个。你们轮流拿石头，一次拿一堆，但是只能拿走最左边或者最右边的石头堆。所有石头被拿完后，谁拥有的石头多，谁获胜。
      
      石头的堆数可以是任意正整数，石头的总数也可以是任意正整数，这样就能打破先手必胜的局面了。比如有三堆石头 piles = [1,100,3]，先手不管拿 1 还是 3，能够决定胜负的 100 都会被后手拿走，后手会获胜。
      
      假设两人都很聪明，请你设计一个算法，返回先手和后手的最后得分（石头总数）之差。比如上面那个例子，先手能获得 4 分，后手会获得 100 分，你的算法应该返回 -96。
    2. 解题思路：
      
      不同问题可以有不同的设计思路，博弈问题的有一个通用设计框架如下：
      
      首先，定义dp数组。dp数组为二维数组，dp数组定义为：i和j表示[i, j]区间的元素，dp[i][j]存储一个元组，认为元组是包含 first 和 second 属性的一个类，first为先手获取的最高分，second为后手获取的最高分。则dp[i][j].first为[i, j]元素中，先手获取的最高分；dp[i][j].second为[i, j]中，后手获取的最高分。我们想求的答案是先手和后手最终分数之差，按照这个定义也就是 dp[0][n−1].first−dp[0][n−1].second
      
      其次，写出状态转移方程。要想写出状态转移方程，必须先找到状态和选择。根据前面对 dp 数组的定义，状态显然有三个：开始的索引 i，结束的索引 j，当前轮到的人。对于这个问题的每个状态，可以做的选择有两个：选择最左边的那堆石头，或者选择最右边的那堆石头。这道题的难点在于，两人是交替进行选择的，也就是说先手的选择会对后手有影响。因此：对于dp[i][j]的选择，选择先手，则之后必定是后手选择，因此在dp[i][j]有两种选择套路左边一堆和右边一堆：left = piples[i] + dp[i + 1][j].second; right = piples[j] + dp[i][j - 1].second;，我们将最大分数的一堆赋值给dp[i][j].first，剩下一个给dp[i][j].second。
      
      最后，确定base case。根据 dp 数组的定义，我们也可以找出 base case，也就是最简单的情况：如果i和j相同，说明只有一个元素，则先手必得分为元素的分，后手得分为0，即dp[i][j].first=piles[i], dp[i][j].second=0;。
      
      我们还需要明白如何遍历状态。状态的遍历可以通过base case和状态转移方程来确定。base case是斜线上dp[i][j]，状态转移方程中的dp[i][j]和dp[i+1][j]和dp[i][j-1]有关。因此，算法不能简单的一行一行遍历 dp 数组，而要斜着遍历数组。
      
      如何斜着遍历数组呢？我们通过如下的模板来斜着遍历数组：
```
 for (int l = 2; l <= n; l++) {
     for (int i = 0; i <= n - 1; i++) {
         int j = l + i - 1;
         // 利用i和j作为索引，斜着遍历
         // 逻辑代码
     }
 }
```

LeetCode算法题

LeetCode算法题
1. 312.【戳气球】
  
  解题思路：
  
  很显然只要涉及求最值，没有任何奇技淫巧，一定是穷举所有可能的结果，然后对比得出最值。因此，如何穷举出所有值就是首先要考虑的。
  
  穷举主要有两种算法，就是回溯算法和动态规划，前者就是暴力穷举，而后者是根据状态转移方程推导「状态」。
  
  首先，先想如何通过回溯算法暴力穷举。我们其实就是想穷举戳气球的顺序，不同的戳气球顺序可能得到不同的分数，我们需要把所有可能的分数中最高的那个找出来，这就是一个「全排列」问题。该思路很容易想到，但是时间复杂度太高，为阶乘级别。
  
  然后，考虑动态规划。动态规划必须满足一个重要条件，即：子问题必须独立。这个问题中我们每戳破一个气球nums[i]，得到的分数和该气球相邻的气球nums[i-1]和nums[i+1]是有相关性的，所以对于这个戳气球问题，如果想用动态规划，必须巧妙地定义dp数组的含义，避免子问题产生相关性，才能推出合理的状态转移方程。
  
  对问题进行一个简单地转化。题目说可以认为nums[-1] = nums[n] = 1，那么我们先直接把这两个边界加进去，形成一个新的数组points，现在气球的索引变成了从1到n，points[0]和points[n+1]可以认为是两个「虚拟气球」。最终，问题就变成了：在一排气球points中，请你戳破气球0和气球n+1之间的所有气球（不包括0和n+1），使得最终只剩下气球0和气球n+1两个气球，最多能够得到多少分？
  
  可以定义dp数组：dp[i][j] = x表示，戳破气球i和气球j之间（开区间，不包括i和j）的所有气球，可以获得的最高分数为x。
  
  base case 就是dp[i][j] = 0，其中0 <= i <= n+1, j <= i+1，因为这种情况下，开区间(i, j)中间根本没有气球可以戳
  
  根据这个dp数组来推导状态转移方程，推导「状态转移方程」，实际上就是在思考怎么「做选择」。该题目第二个难点，就是推导状态转移方程。题目是求戳破气球i和气球j之间的最高分数，如果「正向思考」，就只能写出回溯算法。我们需要「反向思考」，想一想气球i和气球j之间最后一个被戳破的气球可能是哪一个。
  
  气球i和气球j之间的所有气球都可能是最后被戳破的那一个，不防假设为k。这里其实已经找到了「状态」和「选择」：i和j就是两个「状态」，最后戳破的那个气球k就是「选择」。要最后戳破气球k，那得先把开区间(i, k)的气球都戳破，再把开区间(k, j)的气球都戳破；最后剩下的气球k，相邻的就是气球i和气球j，这时候戳破k的话得到的分数就是points[i]*points[k]*points[j]，即dp[i][j] = dp[i][k] + dp[k][j] + points[i]*points[k]*points[j]。对于一组给定的i和j，我们只要穷举i < k < j的所有气球k，选择得分最高的作为dp[i][j]的值即可，这也就是状态转移方程：
```
 dp[i][j] = Math.max(
     dp[i][j], 
     dp[i][k] + dp[k][j] + points[i]*points[j]*points[k]
 );
```
  最后一个问题，如何遍历状态：对于k的穷举仅仅是在做「选择」，但是应该如何穷举「状态」i和j。我们知道，关于「状态」的穷举，最重要的一点就是：状态转移所依赖的状态必须被提前计算出来。在该题中，dp[i][j]所依赖的状态是dp[i][k]和dp[k][j]，那么我们必须保证：在计算dp[i][j]时，dp[i][k]和dp[k][j]已经被计算出来了（其中i < k < j）
  
  关于穷举状态，有个技巧：根据 base case 和最终状态进行推导即可知道如何穷举状态。对于任一dp[i][j]，我们希望所有dp[i][k]和dp[k][j]已经被计算，为了达到这个要求，可以从下到上从左到右遍历

2021/06/03 今日算法

知识点

LeetCode算法题