阅读 96

动态规划之区间类动规

概论

今天再来介绍一类非常经典的动态规划问题,区间类动态规划,这里再说一下,之所以分类讨论动态规划,是为了便于我们根据题意大致确定动态规划的状态以及拆解问题的方向,一类问题的状态定义和拆解问题是有规律可循的,将问题分类为我们提供了一个大致思维导向。

区间类动态规划,其状态定义是和区间有关的,一段区间必须由两个位置确定,我们之前讨论的几种动态规划问题都是只考虑当前位置,比如 矩阵类动态规划 的状态定义就是基于当前的坐标位置,字符匹配类动态规划 虽然有着二维状态数组,但是其表示的是问题 str1(0...i) str2(0...j),因为 i, j 代表的是不同字符串上的位置,你画画表格就会知道,i j 表示的还是当前位置,并不能表示两个位置。

对于判断一道题目是不是区间类动态规划,往往我们不能直接从题目的输入参数中判断出来,输入参数有可能是字符串,也有可能是数组,还有可能是变量加数组等等,确定一道动态规划问题是不是区间类动态规划,需要我们对问题的描述进行判断,往往你可以从题目的问题中找到一些线索,这没什么特别的,其实就是一个熟能生巧的过程,题目见的多了,总结多了,遇到类似的问题基本就可以马上反应过来,但是在这里,我想引出另一个特别重要的知识点,动态规划的另一种实现形式,也就是 记忆化搜索,这可谓是解决动态规划问题的 “万金油”,如果对于一道动规题目,你压根没有任何思路,你都可以尝试着用记忆化搜索的方法来求解,你可能会问,有这么好的方法为什么不早说?虽然记忆化搜索可以帮助你快速切题,但其实这种实现动态规划的方式是有着明显的缺陷的,我这里简单地列了一下:

  • 状态数组无法进行空间优化
  • 递归实现,容易导致 stack overflow
  • 对于时间复杂度的分析,比较不直观
  • 程序 debug 相对来说比较困难,对初学者不友好

那为什么之前不讲解这一方法,非要在这个时候讲解呢?如果你看过之前的文章,你会发现,不管是 矩阵类动规序列类动规,亦或是 字符匹配类动规,这些问题都有一定的套路可言,在问题拆解这一步骤中,我们需要做的也只是线性地去找子问题,或是找相邻的子问题,只要我们写出了递推方程,用简单的 for 循环就可以实现,个人还是比较推荐对于特定的问题,使用特定的方法和分析思路,有些方法适用面是广,但往往并不自然,比如爬楼梯那道题目,递推方程非常直接了当,本来一个 for 循环就可以搞定的事情,你会选择用递归去实现吗?

但是对于区间类动态规划,往往问题和子问题的关系并不是成线性的,而且对于这类问题,即使你得出了递推方程,使用 for 循环去实现也会遇到各种问题,你会发现实现起来不是特别自然,另外,记忆化搜索的自顶向下(后面会讲到)的思考问题的方向非常有助于区间类动态规划的问题拆解,下面,我会用之前的一道例题来讲解一下记忆化搜索,然后,我们会通过几道题目来认识一下区间类动规。


记忆化搜索

记忆化搜索的本质还是动态规划,区别在于思考问题的方向和具体实现上,在思考普通的动态规划问题时,我们习惯性思考 “如何通过子问题推导出当前问题”,这可以说成是一个 从小到大 的过程,而使用记忆化搜索思考问题的时候,我们需要思考 “当前问题如何拆解成子问题”,这是一个 从大到小 的过程,记忆化搜索在实现上其实和分治算法非常相似,不一样之处在于,分治算法解决的问题中并不含有重复子问题,可能我这么说你还是不太理解,那么就让我们通过一道题目具体分析下


LC 120. Triangle

给定一个数组三角形,让你求从上到下的最小路径和。这里,我们先不考虑具体的解法,我们通过题目给的例子来分析一下这个数组三角形:

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

如果我们把这里的每个元素当成一个节点,然后依据题目的意思,
我们可以得到一个图形结构:
          2
         / \
        3   4
       / \ / \
      6   5   7
     / \ / \ / \
    4   1   8   3
复制代码

你会发现这个结构非常类似二叉树,但又不是,因为有些节点有两个父节点,比如上面例子中的 5、1、8,但是这不影响我们使用二叉树的方法去解题,你大可把其想象成一道二叉树问题,题目的问题就变成了 “找出根节点到叶子节点的最短路径和”,模仿求解二叉树问题的方法,我们可以得出下面的代码

public int minimumTotal(List<List<Integer>> triangle) {
    return helper(0, 0, triangle);
}

private int helper(int i, int j, List<List<Integer>> triangle) {
    if (i >= triangle.size() || j < 0 || j >= triangle.get(i).size()) {
        return 0;
    }
    
    // 分
    int left = helper(i + 1, j, triangle);
    int right = helper(i + 1, j + 1, triangle);
    
    // 合
    return triangle.get(i).get(j) + Math.min(left, right);
}
复制代码

你如果熟悉二叉树问题的话,你应该对上面的代码不陌生,这里运用了一个经典的分治思想在里面,用一句话总结分治,那便是 “先分再合”。上面的程序能够再优化吗?如果是二叉树问题,答案是不能,但是如果你回到我们之前画的那个类似二叉树的图形结构,你会发现一个现象就是,这里含有重复子问题,也就是说这里含有一些重复计算,比如路径 2->3->5 和路径 2->4->5 都重复计算了 '5' 这个位置的答案,于是我们将上面的代码进行 “改造”,写出了下面的代码:

public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();

    return helper(0, 0, triangle, new boolean[n][n], new int[n][n]);
}

private int helper(int i, 
                   int j, 
                   List<List<Integer>> triangle,
                   boolean[][] visited,
                   int[][] memo) {
    if (i >= triangle.size() || j < 0 || j >= triangle.get(i).size()) {
        return 0;
    }
    
    if (visited[i][j]) {
        return memo[i][j];
    }
    
    int left = helper(i + 1, j, triangle, visited, memo);
    int right = helper(i + 1, j + 1, triangle, visited, memo);
    
    memo[i][j] = triangle.get(i).get(j) + Math.min(left, right);
    visited[i][j] = true;
    
    return memo[i][j];
}
复制代码

上面的程序就是 记忆化搜索,和之前相比,我们只是增加了一个二维数组帮助我们记录答案,但是我这里想强调的是,和普通动态规划相比,记忆化搜索在思考问题时的一个差别,通过上面的例子,你会发现记忆化搜索强调的是 “拆”,而普通动态则强调的是 “合”,使用记忆化搜索我们一般会从最后要求的结果出发,一步步拆解出子问题并解决,或者可以解释成,记忆化搜索就是动态规划的逆过程,如果你还是不理解,你可以大概认为,一道动态规划问题倒着想就是记忆化搜索,为了进行比较,这里我还是放上使用普通动态规划的代码,你可以对比看看这两者之间的区别,注意观察两种思维方式的起点

public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();
    
    int[][] dp = new int[n][n];
    
    List<Integer> lastRow = triangle.get(n - 1);
    
    for (int i = 0; i < n; ++i) {
        dp[n - 1][i] = lastRow.get(i);
    }
    
    for (int i = n - 2; i >= 0; --i) {
        List<Integer> row = triangle.get(i);
        for (int j = 0; j < i + 1; ++j) {
            dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + row.get(j);
        }
    }
    
    return dp[0][0];
}
复制代码

对于记忆化搜索,这里还有一个技巧可以辅助你解题,那就是 画搜索树,对于上面这道题,搜索树其实就是之前的那个类似二叉树的结构,虽然我知道严格说来这并不是树,如果你愿意,你也可以叫它搜索图,但是名称并不重要,主要是为了辅助你拆解问题。如果你大概了解了记忆化搜索,那么就让我们试着用它来解决区间类动态规划问题吧,看看使用记忆化搜索解决这类问题的优势究竟在哪?


题目分析

LC 516. Longest Palindromic Subsequence

题目解析

求解最长回文序列,也许看到序列,你会考虑使用之前序列类动规的方法去解题,这并没有错,但是你会遇到一个棘手的问题,那就是怎么确定一个区间里面的序列是否是回文的,在 LIS 问题中,我们可以简单地比较当前元素和之前考虑的元素的大小来保证一个序列是递增的,但是对于 “回文” 这个性质并不能这样简单地就保证了,因此在这个地方,可能我们需要换个角度看待问题,还是四个步骤,我们一起来看看

  • 问题拆解

    我们需要求解 str[0...n] 上的最长回文序列的长度,回文就是,字符串中心对称,那么也就是说,一个回文串,它的头尾字符必须相等,在之前的动态规划题目中,我们习惯性思考当前问题可以由哪些相邻的子问题组合而成,在这里,你先不考虑子问题是否相邻或是是否被计算过等,我们重点在于 “”,你会发现,对于问题 str[0...n],只要头尾两个元素相等,我们就可以将头尾去掉,直接看 str[1...n-1],如果头尾不相等,我们必须去掉其中一个元素,从而保证头尾元素有被匹配的可能,在这个地方,如果你还不太熟悉如何去拆解问题,你可以借助记忆化搜索的搜索树来辅助思考

                      str[0...n]
        头尾元素相等 /          \ 头尾元素不相等
             str[1...n-1]    str[0...n-1] and str[1...n]
            /         \             ...
      str[2...n-2]   str[1...n-2] and str[2...n-1]
    复制代码

    到这个地方,问题拆解已经完成

  • 状态定义

    通过上面的 “问题拆解” 部分,我相信你已经知道了这道题是一个和区间相关的问题,因此你可以定义状态 dp[i][j] 表示的是区间 str[i,j] 上的最长回文序列的长度,每当你成功将一个问题归类为区间类动态规划,你都可以尝试去这么定义状态,这就是我们所说的做题的 “套路”。

  • 递推方程

    根据问题拆解和状态定义,递推方程直接可以出来:

    str[i] == str[j]:
    dp[i][j] = dp[i + 1][j - 1] + 2
    
    str[i] != str[j]:
    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])
    复制代码
  • 实现

    有了递推方程,实现是不是就易如反掌了呢?其实并不是,如果你用常规的 for 循环去实现的话,你会感觉写起来不太自然,原因在于,如果按正常的遍历,你无法保证在考虑状态 dp[i][j] 时,子状态 dp[i + 1][j - 1]dp[i + 1][j] 还有 dp[i][j - 1] 已经存有答案,这里,记忆化搜索的优势就体现出来了,用记忆化搜索实现该问题,我们不需要特别在意子问题是否已经计算过,如果没有计算过,直接递归继续往下去计算就好了,计算得到的结果保存在状态数组中,如果碰到计算过的状态直接返回就好,这样我们可以保证一个状态只计算一次,这样,时间复杂度还是 O(n^2),而且使用记忆化搜索,你会发现,实现思路和搜索树中展示拆解问题的思路一模一样。

    基本上你画出了搜索树,记忆化搜索的实现都不会太难,唯一需要考虑的就是初始化的问题,这道题目中,只需考虑 i == j 这一个初始化条件,另外,因为是递归实现,你需要提供递归的出口,这道题目中是 i > j

    如果你硬要用 for 循环去实现,也无可厚非,这里我也放上了 for 循环的参考代码,如果用 for 循环去实现区间类动态规划问题,你还需要在遍历顺序上面下功夫,而且往往这个部分的套路不是特别清晰,不同区间类问题的遍历顺序都不尽相同,因此,这种方法平时可以拿来练练手,找找感觉,但是在面试这种高强度,紧张的环境下,不推荐!

参考代码(记忆化搜索)

public int longestPalindromeSubseq(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }

    int n = s.length();
    int[][] memo = new int[n][n];
    // 求解问题 str(0...n)
    return helper(s.toCharArray(), 0, n - 1, memo);
}

private int helper(char[] sArr, int left, int right, int[][] memo) {
    // 递归的 “出口”,也就是递归的结束条件
    if (left > right) {
        return 0;
    }

    // 如果之前计算过,直接返回答案
    if (memo[left][right] != 0) {
        return memo[left][right];
    }

    // 如果 i == j,单个字符成回文串
    if (left == right) {
        memo[left][right] = 1;
        return memo[left][right];
    }
    
    // 拆解问题
    // 如果 str[i] == [j]: dp[i][j] = dp[i + 1][j - 1] + 2
    if (sArr[left] == sArr[right]) {
        memo[left][right] = helper(sArr, left + 1, right - 1, memo) + 2;
    } 
    // 如果 str[i] != [j]: dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j])
    else {
        memo[left][right] = Math.max(
            helper(sArr, left, right - 1, memo),
            helper(sArr, left + 1, right, memo)
        );
    }
    
    // 返回当前问题的结果
    return memo[left][right];
}
复制代码

参考代码(普通动规)

public int longestPalindromeSubseq(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    
    int n = s.length();
    int[][] dp = new int[n][n];
    
    char[] sArr = s.toCharArray();
    
    for (int i = n - 1; i >= 0; --i) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; ++j) {
            if (sArr[i] == sArr[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[0][n - 1];
}
复制代码

LC 312. Burst Balloons

题目解析

给一个数组,数组里面的值表示的是气球的价值,每打爆一个气球,获得的价值是当前气球的价值和左右相邻气球的价值之积,如果左边或者右边没有剩余气球,那么左边或者右边对应乘上 1 就好,题目问怎样打气球才能获得最高价值,输出这个价值,老样子,四个步骤走一遍:

  • 问题拆解

    这道题目有一个很头疼的问题在于,数组是动态变化的,比如题目给的例子:

    Input: [3,1,5,8]
    Output: 167 
    Explanation: nums  = [3,1,5,8] --> [3,5,8] -->  [3,8]   -->  [8]  --> []
                 coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
    复制代码

    数组当中的元素在逐渐减少,如果你尝试着找子问题,然后从子问题推导当前问题,你会发现这种思考方式会把问题变得非常复杂,如果我们 倒着想,则会省去很多不必要的麻烦,还是借着题目给的例子,我们一起看看:

    Input: [3,1,5,8]
    
    不管输入是什么,到最后所有的气球都会被打爆,数组为空
    因此,我们从最后的结果出发,倒着去看问题的拆解
              
                                            []
             [3]                   [1]                [5]                [8]
           [1,5,8]              [3]  [5,8]         [3,1]  [8]          [3,1,5]
           ...                  ...                ...                ...
    复制代码

    上面这个是一个搜索树,这里我没有用下标的形式表示区间,可能你看的不是太懂,我解释一下,不管你选择什么样的方案,最后的结果都是 “气球全部被打爆”,我们从这个结果出发往下推,自然而然想到 “最后一个被打爆的气球是哪一个?”,有可能是 3,1,5,8 中的任意一个,这里我们就要分情况讨论了,比如说,最后一个打爆的气球是 5,那么在打爆 5 之前,区间 [3,1] 和 区间 [8] 中的所有气球均已全部打爆,那么,紧接着的问题就是 倒数第二个被打爆的气球是哪个? 有可能是 3,1,8 中的一个,这里我们其实可以把区间当成整体去思考,如果这样做的话,你会发现,我们已经将问题 “打爆区间 [3,1,5,8] 获得的最大价值是多少” 拆解成了 “打爆区间 [3,1] 以及区间 [8] 所获得的最大价值分别是多少”,而且,这里有个地方特别有意思,就是区间 [3,1] 和区间 [8] 之间隔着最后打爆的元素 5,这两个区间谁先被打爆,谁后被打爆并没有关系。

    你会发现,倒着想,在拆解问题中,我们自然而然地可以画出搜索树,然后你也可以清晰地发现这里存在着 重复子问题,搜索树一出来,基本上问题就算是拆解完成了。

  • 状态定义

    在定义状态之前,你首先要对你当前解决的问题归类,这道题目中,区间这一特性其实非常明显,因此我们定义 dp[i][j] 表示打爆区间 array[i...j] 中所有气球所获的的最大价值

  • 递推方程

    根据前面的问题拆解和状态定义,我们可以得出递推方程:

    dp[i][j] = Math.max(
      array[l] * array[i - 1] * array[j + 1] + dp[i][l - 1] + dp[l + 1][j],
      ...
      array[r] * array[i - 1] * array[j + 1] + dp[i][r - 1] + dp[r + 1][j]
    )
    其中 i <= l, r <= j
    复制代码

    上面的推导关系式可能并不是特别好理解,这里我解释一下,一个区间当中都有一个最后被打爆的气球,并且一个区间中的任意元素均可能是最后打爆的,我们选择最后一个被打爆的气球后,需要加上这个气球的左区间和右区间的状态才会是当前区间的状态。

  • 实现

    在上面的递推方程中,array[l] * array[i - 1] * array[j + 1] 表示最后打爆的气球乘上了区间外的两个相邻气球,这也就说明,当前我们考虑的区间相比旁边的区间是最先打爆的,这个顺序要如何保证,如果你仔细看搜索树,你会发现,递归保证了这一特性。时间上面,因为要考虑 n^2 个区间,然后每个区间要选择最后一个被打爆的气球,这么算下来就是 O(n^3)

    在这道题目中,记忆化搜索的优势可谓体现的淋漓尽致,这里我还是放上普通动态规划的实现代码,你可以对比看看。

参考代码(记忆化搜索)

public int maxCoins(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    int[][] dp = new int[nums.length][nums.length];
    
    return helper(nums, dp, 0, nums.length - 1);
}

private int helper(int[] nums, int[][] dp, int l, int r) {
    if (l > r) {
        return 0;
    }
    
    if (dp[l][r] != 0) {
        return dp[l][r];
    }
    
    int max = nums[l];
    for (int i = l; i <= r; ++i) {
        int cur = helper(nums, dp, l, i - 1)
                    + get(nums, l - 1) * nums[i] * get(nums, r + 1)
                    + helper(nums, dp, i + 1, r);
        
        max = Math.max(max, cur);
    }
    
    dp[l][r] = max;
    
    return max;
}

private int get(int[] nums, int i) {
    if (i < 0 || i >= nums.length) {
        return 1;
    }
    
    return nums[i];
}
复制代码

参考代码(普通动规)

public int maxCoins(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    int[] newNums = new int[nums.length + 2];
    
    newNums[0] = newNums[nums.length + 1] = 1;
    for (int i = 0; i < nums.length; ++i) {
        newNums[i + 1] = nums[i];
    }
    
    int n = newNums.length;
    
    int[][] dp = new int[n][n];

    for (int i = 2; i < n; ++i) {
        for (int l = 0; l < n - i; ++l) {
            int r = l + i;
            for (int j = l + 1; j < r; ++j) {
                dp[l][r] = Math.max(dp[l][r], 
                             newNums[l] * newNums[j] * newNums[r] 
                                    + dp[l][j] + dp[j][r]);
            }
        }
    }
    
    return dp[0][n - 1];
}
复制代码

总结

区间类动态规划就讲到这里,区间类的题目也不少,比如经典的石子合并问题,LeetCode 上面也有相关的题目,比如 Scramble StringMinimum Cost to Merge Stones 等等,这些题目的难度均不低,做不出来也不用气馁,多练多想就是了。我们也讲了记忆化搜索这种用搜索的形式去实现动态规划的方法,它给我们解动态规划问题提供了新的思路,总结下来就是:

  • 搜索树非常直观,可以很好地辅助思考和拆解问题
  • 遇到不会的问题,从结果出发,倒着想,往往有奇效

记忆化搜索可以解决绝大多数的动态规划问题,是解决动态规划问题的 “万金油”,即使这样,我还是建议你针对具体的问题,选择合适的方法,多多学习并尝试不同的方法,用不同的视角看问题,这样学习算法会变得更加有趣。

关注下面的标签,发现更多相似文章
评论