动态规划(Dynamic Programming)算法框架
洪笳淏 Lv4
 2021-04-11 15:30:30      

  在一开始学习算法的时候，我对动态规划和贪心算法一直都只有个模糊的概念，不明白两者到底有什么区别，感觉思路都差不太多。于是在本文的开头，我想对比一下贪心算法和动态规划的区别和联系。动态规划和贪心算法都是用来求最优化问题，且二者都必须具有最有子结构。动态规划的整体策略是一种自底向上的结构，贪心算法是自顶向下的结构。贪心算法可以解决的问题，动态规划都能解决，可以说，贪心算法是动态规划的一个特例。贪心算法和动态规划最大的不同在于，它并不是首先寻找子问题的最优解，然后在其中进行选择，而是首先做一次贪心选择——在当时（局部）看来最有选择——然后求解选出的子问题，从而不必费心求解所有可能相关的子问题。

  动态规划具有两个性质：1）重叠子问题；2）最优子结构*。贪心算法具有的两个性质：1）贪心选择性质；2）最优子结构*。动态规划就是为了消除其重叠子问题而设计的。其实贪心算法是一种特殊的动态规划，由于其具有贪心选择性质，保证了子问题只会被计算一次，不会被多次计算，因此贪心算法其实是最简单的动态规划。

算法框架

动态规划(DP)思维框架

  首先引用📋《labuladong的算法小抄》中对动态规划问题的分析。

  动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离等等。既然目标是求最值，那么DP的核心问题就是穷举。动态规划的穷举是很特别的，它存在以下三要素：

  • 重叠子问题：如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
  • 最优子结构：动态规划问题一定具备最优子结构，才能通过子问题的最值得到原问题的最值。
  • 状态转移方程：动态规划问题的难点和关键，找到正确的状态转移方程，问题基本就能得到解决。

  由此可以得到一个基本的思维框架用于解决这类问题：明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

  按上面的套路走，最后的结果就可以套这个框架：

1
2
3
4
5
6
7
// 初始化 base case
dp[0][0][...] = base
// 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

  下面通过斐波那契数列问题和凑零钱问题来详解动态规划的基本原理。前者主要是让你明白什么是重叠子问题（斐波那契数列没有求最值，所以严格来说不是动态规划问题），后者主要举集中于如何列出状态转移方程。

动态规划杀手锏

动态规划需要注意的要点：

  • “问5”法则判断问题是否是动态规划，例如最优解，最小或者最大等等；

  • 如果判断属于动态规划的话，接下来我们可以根据“问4”法则求解：

    • 状态（小规模问题的数学表示）
    • 状态转移方程（大规模问题如何转化为更小的问题）
    • 最小状态（最小规模的问题）
    • 要求的返回值是什么

杀手锏

1）建模：

  • 最优子结构

  • 状态转移方程

  • 边界

2）实现：

  • 暴力递归

  • 备忘录法（从上倒下，非全二叉树，hash保存！）

  • 自底而上（迭代实现）

斐波那契数列

1.暴力递归

斐波那契数列的数学形式就是递归的，写成代码就是这样：

1
2
3
4
5
6
func fib(N int) int {
  if N == 1 || N==2 {
    return 1
  }
  return fib(N-1)+fib(N-2)
}

  这个不用多说了，学校老师讲递归的时候似乎都是拿这个举例。我们也知道这样写代码虽然简洁易懂，但是十分低效，低效在哪里？假设 n = 20，请画出递归树：

avatar

PS：但凡遇到需要递归的问题，最好都画出递归树，这对你分析算法的复杂度，寻找算法低效的原因都有巨大帮助。

  这个递归树怎么理解？就是说想要计算原问题 f(20)，我就得先计算出子问题 f(19) 和 f(18)，然后要计算 f(19)，我就要先算出子问题 f(18) 和 f(17)，以此类推。最后遇到 f(1) 或者 f(2) 的时候，结果已知，就能直接返回结果，递归树不再向下生长了。递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间。首先计算子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。

  观察递归树，很明显发现了算法低效的原因：存在大量重复计算，比如 f(18) 被计算了两次，而且你可以看到，以 f(18) 为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间。更何况，还不止 f(18) 这一个节点被重复计算，所以这个算法及其低效。

  这就是动态规划问题的第一个性质：重叠子问题。下面，我们想办法解决这个问题。

2.带备忘录的递归解法

  即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func fib(N int) int{
  if N < 1 {
    return 0
  }
  // 备忘录全初始化为 0
  mem := make([]int, N+1)
  // 进行带备忘录的递归
  return helper(mem, N)
}

func helper(mem []int, N int) int {
  // base case
  if N == 1 || N == 2 {
    return 1
  }
  
  // 已经计算过
  if mem[N] != 0 {
    return mem[N]
  }
  // 更新备忘录
  mem[N] = help(N-1)+help[N-2]
  return mem[N]
}

现在，画出递归树，你就知道「备忘录」到底做了什么。

avatar

  实际上，带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。子问题个数，即图中节点的总数，由于本算法不存在冗余计算，子问题就是 f(1), f(2), f(3) … f(20)，数量和输入规模 n = 20 成正比，所以子问题个数为 O(n)。所以，本算法的时间复杂度是 O(n)。比起暴力算法，是降维打击。

  至此，带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上，这种解法和迭代的动态规划已经差不多了，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」。

  啥叫「自顶向下」？注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案，这就叫「自顶向下」。

avatar

  啥叫「自底向上」？反过来，我们直接从最底下，最简单，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。

3.DP数组的迭代解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func fib(N int) int {
  if N < 1 {
    return 0
  }
  if N == 1 || N == 2 {
    return 1
  }
  dp := make([]int, N+1)
  
  // 初始化base case
  dp[1], dp[2] = 1, 1
  for i:=3; i<=N; i++ {
    dp[i] = dp[i-1]+dp[i-2]  // 状态转移方程
  }
  return dp[N]
}

avatar

  画个图就很好理解了，而且你发现这个 DP table 特别像之前那个「剪枝」后的结果，只是反过来算而已。实际上，带备忘录的递归解法中的「备忘录」，最终完成后就是这个 DP table，所以说这两种解法其实是差不多的，大部分情况下，效率也基本相同。

这里，引出「状态转移方程」这个名词，实际上就是描述问题结构的数学形式：

avatar

  为啥叫「状态转移方程」？其实就是为了听起来高端。你把 f(n) 想做一个状态 n，这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来，这就叫状态转移，仅此而已。

  你会发现，上面的几种解法中的所有操作，例如 return f(n - 1) + f(n - 2)，dp[i] = dp[i - 1] + dp[i - 2]，以及对备忘录或 DP table 的初始化操作，都是围绕这个方程式的不同表现形式。可见列出「状态转移方程」的重要性，它是解决问题的核心。而且很容易发现，其实状态转移方程直接代表着暴力解法。

  千万不要看不起暴力解，动态规划问题最困难的就是写出这个暴力解，即状态转移方程。只要写出暴力解，优化方法无非是用备忘录或者 DP table，再无奥妙可言。

  这个例子的最后，讲一个细节优化。细心的读者会发现，根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func fib(N int) int {
  if N < 1 {
    return 0
  }
  if N == 1 || N == 2 {
    return 1
  } 
  prev := 1
  curr := 1
  for i:=3; i<=N; i++ {
    sum := prev + curr // 新状态由前两个状态之和求得
    prev = curr  // 保存当前状态
    curr = sum   // 保存前一个状态
  }
  return curr
}

  这个技巧就是所谓的「状态压缩」，如果我们发现每次状态转移只需要 DP table 中的一部分，那么可以尝试用状态压缩来缩小 DP table 的大小，只记录必要的数据，上述例子就相当于把DP table 的大小从 n 缩小到 2。后续的动态规划章节中我们还会看到这样的例子，一般来说是把一个二维的 DP table 压缩成一维，即把空间复杂度从 O(n^2) 压缩到 O(n)。

  至于动态规划的另一个重要特性「最优子结构」，下面会涉及。斐波那契数列的例子严格来说不算动态规划，因为没有涉及求最值，以上旨在说明重叠子问题的消除方法，演示得到最优解法逐步求精的过程。下面，看第二个例子，凑零钱问题。

凑零钱问题

  给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。算法的函数签名如下：

1
2
// coins 中是可选硬币面值，amount 是目标金额
func coinChange(coins []int, amount int) int

  这个问题是动态规划问题，因为它具有「最优子结构」的。要符合「最优子结构」，子问题间必须互相独立。为什么说它符合最优子结构呢？比如你想求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10 的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的硬币）就是原问题的答案。因为硬币的数量是没有限制的，所以子问题之间没有相互制，是互相独立的。

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
func coinChange(coins []int, amount int) int {
  return dp(coins []int, amount int)
}

func dp(coins []int, n int){
  if n == 0 {
    return 0
  }
  if n < 0 {
    return -1
  }
  res := n+1
  for _,value := range coins {
    subproblem := dp [n-value]
    if subproblem == -1 {
      continue
    }
    res = min(res, 1 + subproblem)
  }
  return res
}

func min(a, b int) int {
  if a < b {
    return a
  } else {
    return b
  }
}

至此，这个问题其实就解决了，只不过需要消除一下重叠子问题，比如 amount = 11, coins = {1,2,5} 时画出递归树看看:

avatar

递归算法的时间复杂度分析：子问题总数 x 每个子问题的时间。

子问题总数为递归树节点个数，这个比较难看出来，是 O(n^k)，总之是指数级别的。每个子问题中含有一个 for 循环，复杂度为 O(k)。所以总时间复杂度为 O(k * n^k)，指数级别。

2.带备忘录的递归

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
func coinChange(coins []int, amount int) int {
  mem := make([]int, amount+1)
  for i:=0; i<len(mem); i++ {
    mem[i] = amount+1
  }
  return dp(coins, amount, mem)
}

func dp(coins []int, n int, mem []int){
  if n == 0 {
    return 0
  }
  if n < 0 {
    return -1
  }
  if mem[n] < n+1 {
    return mem[n]
  }
  res := n+1
  for _,value := range coins {
    subproblem := dp [coins, n-value, mem]
    if subproblem == -1 {
      continue
    }
    
    res = min(res, 1 + subproblem)
  }
  mem[n] = res
  return res
}

func min(a, b int) int {
  if a < b {
    return a
  } else {
    return b
  }
}

  「备忘录」大大减小了子问题数目，完全消除了子问题的冗余，所以子问题总数不会超过金额数 n，即子问题数目为 O(n)。处理一个子问题的时间不变，仍是 O(k)，所以总的时间复杂度是 O(kn)。

3.dp 数组的迭代解法(推荐)

  迭代就是将递归转化成for循环。

  dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。

根据我们文章开头给出的动态规划代码框架可以写出如下解法：

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
func coinChange(coins []int, amount int) {
  if amount < 0 {
    return -1
  }
  
  // 数组大小为 amount + 1，初始值也为 amount + 1
  dp := make([]int, amount+1)
  for i:=0; i<len(dp); i++ {
    dp[i] = amount+1
  }
  
  // base case
  dp[0] = 0
  
  // 外层 for 循环在遍历所有状态的所有取值
  for i:=1; i<=amount; i++ {
    // 内层 for 循环在求所有选择的最小值
    for _, value := range coins {
      if i-value < 0 { // 子问题无解，跳过
        continue
      }
      dp[i] = min(dp[i], 1+dp[i-value])  // 状态转移方程
    }
  }
  if dp[amount] == amount+1 { // 说明没有合适的方案
    return -1
  }
  return dp[amount]
}

func min(a,b int) {
  if a<b {
    return a
  } else {
    return b
  }
}

  PS：为啥 dp 数组初始化为 amount + 1 呢，因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），所以初始化为 amount + 1 就相当于初始化为正无穷，便于后续取最小值。

实际案例

最小路径和

  给定一个包含非负整数的 m*n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

avatar

1
2
3
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

1
2
输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

1
2
3
4
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

算法思路：由于路径的方向只能是向下或向右，因此网格的第一行的每个元素只能从左上角元素开始向右移动到达，网格的第一列的每个元素只能从左上角元素开始向下移动到达，此时的路径是唯一的，因此每个元素对应的最小路径和即为对应的路径上的数字总和。

对于不在第一行和第一列的元素，可以从其上方相邻元素向下移动一步到达，或者从其左方相邻元素向右移动一步到达，元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值。由于每个元素对应的最小路径和与其相邻元素对应的最小路径和有关，因此可以使用动态规划求解。

创建二维数组dp，与原始网格的大小相同，*dp[i] [j]表示从左上角出发到(i,j)位置的最小路径和。显然，dp[0] [0]=grid[0] [0]*。对于 dp 中的其余元素，通过以下状态转移方程计算元素值。

1
2
3
当 i>0 且 j=0 时，dp[i][0]=dp[i−1][0]+grid[i][0]。
当 i=0 且 j>0 时，dp[0][j]=dp[0][j−1]+grid[0][j]。
当 i>0 且 j>0 时，dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]。

最后得到 *dp[m−1] [n−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
func minPathSum(grid [][]int) int {
    dp := make([][]int, len(grid)) // 初始化切片的行
    for i:=0; i<len(grid); i++ { // 初始化切片的列
        dp[i] = make([]int, len(grid[0]))
    }

    dp[0][0] = grid[0][0] // 初始化起始点值
    for i:=1; i<len(grid[0]); i++ { // 初始化第一行的值
        dp[0][i] = grid[0][i]+dp[0][i-1]
    }
    for i:=1; i<len(grid); i++ { //初始化第一列的值
        dp[i][0] = grid[i][0]+dp[i-1][0]
    }

    if len(grid) == 1 && len(grid[0]) == 1 {
        return grid[0][0]
    }
    if len(grid) == 1 {
        return dp[0][len(grid[0])-1]
    }
    if len(grid[0]) == 1 {
        return dp[len(grid)-1][0]
    }
    for i:=1; i<len(grid); i++ {
        for j:=1; j<len(grid[0]); j++ {
            dp[i][j] = min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]) // 状态转移方程
        }
    }
    return dp[len(grid)-1][len(grid[0])-1]
}

func min(a,b int) int {
    if a<b {
        return a
    } else {
        return b
    }
}

接雨水

  给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

rainwatertrap

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

算法思路：对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 *height[i]*。

朴素的做法是对于数组 height 中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。假设数组 height 的长度为 n，该做法需要对每个下标位置使用 O(n) 的时间向两边扫描并得到最大高度，因此总时间复杂度是 *O(n2)*。

上述做法的时间复杂度较高是因为需要对每个下标位置都向两边扫描。如果已经知道每个位置两边的最大高度，则可以在 O(n) 的时间内得到能接的雨水总量。使用动态规划的方法，可以在 O(n) 的时间内预处理得到每个位置两边的最大高度。

创建两个长度为 n 的数组 leftMax 和 rightMax。对于 0≤i<n，leftMax[i] 表示下标 i 及其左边的位置中，height 的最大高度，rightMax[i] 表示下标 i 及其右边的位置中，height 的最大高度。显然，*leftMax[0]=height[0]*，
*rightMax[n−1]=height[n−1]*。两个数组的其余元素的计算如下：

  • 当 1≤i≤n−1 时，*leftMax[i]=max(leftMax[i−1],height[i])*；
  • 当 0≤i≤n−2 时，*rightMax[i]=max(rightMax[i+1],height[i])*。

因此可以正向遍历数组 height 得到数组 leftMax 的每个元素值，反向遍历数组 height 得到数组 rightMax 的每个元素值。在得到数组 leftMax 和 rightMax 的每个元素值之后，对于 0≤i<n，下标 i 处能接的雨水量等于
*min(leftMax[i],rightMax[i])−height[i]*。遍历每个下标位置即可得到能接的雨水总量。动态规划做法可以由下图体现。

avatar

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
func trap(height []int) int {
    l := len(height)
    if l == 0 {
        return 0
    }
    leftMax := make([]int, l)
    rightMax := make([]int, l)
    leftMax[0] = height[0]
    rightMax[l-1] = height[l-1]

    for i:=1; i<l; i++ {  // 从左向右遍历，得到i位置处左边的最高值
        leftMax[i] = max(leftMax[i-1],height[i])
    }

    for i:=l-2; i>=0; i-- { // 从右向左遍历，得到i位置处右边的最高值
        rightMax[i] = max(rightMax[i+1],height[i])
    }

    ret := 0
    for i:=0; i<l; i++ {
        ret += min(leftMax[i],rightMax[i])-height[i]
    }
    return ret
}

func min(a,b int) int {
    if a<b {
        return a
    } else {
        return b
    }
}

func max(a,b int) int {
    if a>b {
        return a
    } else {
        return b
    }
}

最长回文子串【字节每日一题】

  给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

示例 3：

1
2
输入：s = "a"
输出："a"

示例 4：

1
2
输入：s = "ac"
输出："a"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母（大写和/或小写）组成

解题思路：

  对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 “ababa”，如果我们已经知道 “bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是 “a”。据这样的思路，我们就可以用动态规划的方法解决本题。我们用 dp(i,j) 表示字符串 s 的第 i 到 j 个字母组成的串（下文表示成 s[i:j]）是否为回文串：

avatar

这里的「其它情况」包含两种可能性：

  • s[i,j] 本身不是一个回文串；

  • i>j，此时 s[i,j]本身不合法。

那么我们就可以写出动态规划的状态转移方程：

avatar

也就是说，只有 s[i+1:j−1] 是回文串，并且 s 的第 i 和 j 个字母相同时，s[i:j] 才会是回文串。上文的所有讨论是建立在子串长度大于 2 的前提之上的，我们还需要考虑动态规划中的边界条件，即子串的长度为 1 或 2。对于长度为 1 的子串，它显然是个回文串；对于长度为 2 的子串，只要它的两个字母相同，它就是一个回文串。因此我们就可以写出动态规划的边界条件：

avatar
注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。

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
func longestPalindrome(s string) string {
    n := len(s)
    dp := make([][]bool,n)

    for i :=0; i<n; i++ {
        dp[i] = make([]bool,n)
    }

    for i:=0; i<n; i++ {
        dp[i][i] = true
    }

    length := 0
    subStr := s[:1]

    for L:=2; L<=n; L++ {
        for i:=0; i<=n-L; i++ {
            j := i+L-1

            if s[i] != s[j] {
                dp[i][j] = false
            } else {
                if L == 2 {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i+1][j-1]
                }
            }


            if dp[i][j] && j-i+1 > length {
                length = j-i+1
                subStr = s[i:j+1]
            }
        }
    }
    return subStr
}

32. 最长有效括号【字节每日一题】

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

1
2
3
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

1
2
3
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

1
2
输入：s = ""
输出：0

提示：

  • 0 <= s.length <= 3 * 104
  • s[i] 为 '(' 或 ')'

解题思路：

  结合题目，有最长这个字眼，可以考虑尝试使用 动态规划 进行分析。这是一个 最值型 动态规划的题目。

动态规划题目分析的 4 个步骤：

  • 确定状态
    • 研究最优策略的最后一步
    • 化为子问题
  • 转移方程
    • 根据子问题定义得到
  • 初始条件和边界情况
  • 计算顺序

  首先，我们定义一个 dp 数组，其中第 ii 个元素表示以下标为 i 的字符结尾的最长有效子字符串的长度。

  • 确定状态：

最后一步：

对于最优的策略，一定有最后一个元素 s[i]。所以，我们先看第 i 个位置，这个位置的元素 s[i]可能有如下两种情况：

  • s[i]=='(' : 这时，s[i]s[i] 无法和其之前的元素组成有效的括号对，所以，dp[i] = 0

  • s[i]==')'：这时，需要看其前面对元素来判断是否有有效括号对。

    • 情况1:s[i−1]=='('

      即 s[i] 和 s[i−1] 组成一对有效括号，有效括号长度新增长度2，i位置对最长有效括号长度为 其之前2个位置的最长括号长度加上当前位置新增的2，我们无需知道 i−2 位置对字符是否可以组成有效括号对。那么有：dp[i]=dp[i−2]+2

      avatar

    • 情况2:s[i-1]==')'

      这种情况下，如果前面有和 s[i] 组成有效括号对的字符，即形如 ((....))，这样的话，就要求 s[i−1]位置必然是有效的括号对，否则 s[i] 无法和前面对字符组成有效括号对。这时，我们只需要找到和 s[i] 配对对位置，并判断其是否是 ( 即可。和其配对对位置为：i−dp[i−1]−1。

      如果：s[i−dp[i−1]−1]=='(' :

      有效括号长度新增长度2，ii位置对最长有效括号长度为 i-1位置的最长括号长度加上当前位置新增的2，那么有：dp[i]=dp[i−1]+2。值得注意的是，i−dp[i−1]−1 和 i 组成了有效括号对，这将是一段独立的有效括号序列，如果之前的子序列是形如 (...) 这种序列，那么当前位置的最长有效括号长度还需要加上这一段。所以：dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2

      avatar

  • 子问题：设dp数组，其中第 i 个元素表示以下标为 i 的字符结尾的最长有效子字符串的长度。

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
func longestValidParentheses(s string) int {
    n := len(s)
    dp := make([]int,n)
    max := 0

    for i:=1; i<n; i++ {
        if s[i] == '(' {
            dp[i] = 0
        } else if s[i] == ')' {
            if s[i-1] == '(' {
                if i<=2 {
                    dp[i] = 2
                } else {
                    dp[i] = dp[i-2] + 2
                }
            } else if s[i-1] == ')' {
                if i-dp[i-1]-1 >= 0 && s[i-dp[i-1]-1] == '(' {
                    if i-dp[i-1]-2 > 0 {
                        dp[i] = dp[i-1]+dp[i-dp[i-1]-2]+2
                    } else {
                        dp[i] = dp[i-1]+2
                    }
                }
            }
        }

        if dp[i] > max {
            max = dp[i]
        }
    }
    return max
}

总结

  计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。列出动态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。备忘录、DP table 就是在追求“如何聪明地穷举”。用空间换时间的思路，是降低时间复杂度的不二法门。

参考资料

1.动态规划解题套路框架

2.动态规划和贪心算法的区别

3.【数据结构】贪心算法和动态规划

  • Post title：动态规划(Dynamic Programming)算法框架
  • Post author：洪笳淏
  • Create time：2021-04-11 15:30:30
  • Post link：https://jiahaohong1997.github.io/2021/04/11/动态规划(Dynamic-Programming)算法框架/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments