【动态规划】（六）区间动态规划

区间动态规划一般用在单串问题上，以区间 [i, j] 为单位思考状态的设计和转移。一般是定义 dp[i][j]，表示考虑 [i..j] 范围内的元素，原问题的解，增加 i或减小 j 都可以得到更小规模的子问题。它与线性动态规划在状态设计和状态转移上都有明显的不同，但由于这两个方法都经常用在单串问题上，导致我们拿到一个单串的问题时，经常不能快速反映出应该用哪种方法。这是区间动态规划的难点之一，但是这个难点也是好解决的，就是做一定数量的练习题，因为区间动态规划的题目比线性动态规划少很多，并且区间动态规划的状态设计和转移都比较朴素，变化也比线性动态规划少很多，所以通过不多的题目数量就可以把区间动态规划常见的方法和变化看个大概了。

1 回文相关问题

回文系列问题是区间动态规划的典型问题，这里整理了一系列与回文有关的问题。

最长回文子串

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

因为题目要求返回回文串，而不是长度，因此我们需要定义状态 $dp[i][j]$ 表示区间 s[i, j] 是否是回文串，状态转移非常简单：

如果 s[i] == s[j]，dp[i][j] = dp[i+1][j-1]
如果 s[i] != s[j]，dp[i][j] = false

边界条件：任意一个字母都是回文串，因此 dp[i][i] = true。

编码时我们不好同时枚举左边界和右边界，考虑到我们一定是从长度较短的回文串推导出长度较长的回文串，所以可以枚举子串长度，对每一个长度枚举左边界，自然就可以确定右边界了，其他编码的细节见代码：

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, 0));
        for(int i = 0; i < n; ++i)
        {
            dp[i][i] = 1;
        }
        int beg = 0, maxlen = 1;
        for(int L = 2; L <= n; ++L)
        {
            for(int i = 0; i < n; ++i)
            {
                int j = i + L - 1;
                if(j >= n) break;
                dp[i][j] = L < 3 ? s[i] == s[j] : dp[i+1][j-1] && s[i] == s[j];
                if(dp[i][j] && j - i + 1 > maxlen)
                {
                    maxlen = j - i + 1;
                    beg = i;
                }
            }
        }
        return s.substr(beg, maxlen);
    }
};

这道题比较简单，用动态规划无论是时间还是空间开销都比较大，但是观察上面的动态规划过程我们会发现，所有的状态都是从边界条件转移而来的并且是唯一的，因此我们只要枚举所有边界情况，然后从这个边界状态开始扩展，直到无法继续扩展就得到了一个回文子串，最后返回最长的一个即可。

边界情况对应的就是长度为 1 和 2 的子串，这些子串作为回文中心，可以不断向两边扩展，直到不是回文串就停止扩展，因此我们只要枚举所有的回文中心并向两边扩展即可。

class Solution {
public:
    pair<int, int> expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
        }
        return {left + 1, right - 1};
    }

    string longestPalindrome(string s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.size(); ++i) {
            auto [left1, right1] = expandAroundCenter(s, i, i); 	//长度为1的回文中心
            auto [left2, right2] = expandAroundCenter(s, i, i + 1); //长度为2的回文中心
            if (right1 - left1 > end - start) {
                start = left1;
                end = right1;
            }
            if (right2 - left2 > end - start) {
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end - start + 1);
    }
};

回文子串

给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。

上一题的简化版本，不多赘述，直接用中心扩展方法：

class Solution {
public:
    int ans = 0;
    void expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
            ++ans;
        }
    }
    int countSubstrings(string s) {
        for (int i = 0; i < s.size(); ++i) {
            expandAroundCenter(s, i, i); 		//长度为1的回文中心
            expandAroundCenter(s, i, i + 1); 	//长度为2的回文中心
        }
        return ans;
    }
};

最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

这是区间动态规划最经典的问题了，按照最常规的思路去做就可以。定义状态 $dp[i][j]$ 表示 s[i, j] 区间内最长回文子序列长度，状态转移：

如果 s[i] == s[j] ，dp[i][j] = dp[i+1][j-1] + 2
如果 s[i] != s[j] ，dp[i][j] = max(dp[i+1][j], max(dp[i][j-1], dp[i+1][j-1]))，由于dp[i+1][j] 和 dp[i][j-1]是包含 dp[i+1][j-1] 的，这与我们的状态定义有关，因此只需要取 dp[i+1][j] 和 dp[i][j-1] 之间的最大值即可。

边界条件同样是 dp[i][i] = 1，遍历时记得要从较短的子串开始遍历，因此我们从后向前遍历：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for(int i = 0; i < n; ++i)
        {
            dp[i][i] = 1;
        }
        for(int i = n - 1; i >=0; --i)
        {
            for(int j = i + 1; j < n; ++j)
            {
                if(s[j] == s[i]) dp[i][j] = dp[i+1][j-1] + 2;
                else dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
            }
        }
        return dp[0][n-1];
    }
};

让字符串成为回文串的最少插入次数

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

这也是一道典型的区间动态规划问题，但相对困难。动态规划定义依然是 $dp[i][j]$ 表示使得 s[i, j] 成为回文串的最小操作次数。我们可以从外向内推导，因为如果最外层两个字符相等，那么最外层就已经是回文了，不需要额外操作，只要保证内层也是回文即可，因此 dp[i][j] = dp[i+1][j-1]；而如果最外层两个字母不相等，要使 s[i, j] 成为回文串，要么在右边插入一个 s[i] ，要么在左边插入一个 s[j] ，所以此时 dp[i][j] = min(dp[i+1][j] + 1, dp[i][j-1] + 1)。

边界条件还是 dp[i][i] = 0，单个字符本身就形成回文，不需要额外操作。

遍历时和之前一样，可以通过枚举长度和左边界的方式确定右边界。

class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for (int span = 2; span <= n; ++span) {
            for (int i = 0; i <= n - span; ++i) {
                int j = i + span - 1;
                dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
                if (s[i] == s[j]) {
                    dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

此外本题还可以用线性动态规划解决，具体可看官方题解方法一，但没有区间动态规划容易理解，也不好想到。

段式回文

你会得到一个字符串 $text$ 。你应该把它分成 $k$ 个子字符串 $(subtext_1, subtext_2, …,subtext_k)$ ，要求满足:

$subtext_i$ 是非空字符串

所有子字符串的连接等于 $text$ ( 即$subtext_1 + subtext_2 + … + subtext_k == text$ )

$subtext_i == subtext_{k - i + 1},\ 1 \leq i \leq k$

返回 $k$ 可能最大值。

题目的意思是把一个字符串分成多段，所有段之间满足回文关系，比如：

输入：text = “ghiabcdefhelloadamhelloabcdefghi”
输出：7
解释：我们可以把字符串拆分成 “(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)”。

这道题用动态规划做比较困难，但用贪心的思想非常简单，因为首尾两端字符串回文意味着他们相等，因此它们的长度也必须相等，那么我们遍历所有长度，也就是从 1 到 text.szie() / 2，然后判断首尾这么长的字符串是否相等，如果相等就把这两段剪掉，剩下的字符串继续这么判断，这样最终得到的分段数就是最大分段数 k。

class Solution {
private:
    bool isEqual(const string& text, int i1, int i2, int len)
    {
        for (int i = 0; i < len; ++i)
        {
            if (text[i1+i] != text[i2+i])
            {
                return false;
            }
        }

        return true;
    }
public:
    int longestDecomposition(string text) {
        int n = text.size();
        for (int i = 1; i <= (n >> 1); ++i)
        {
            //相当于 if (text.substr(0, i) == text.substr(n-i, n))
            if (isEqual(text, 0, n-i, i))
            {
                return 2 + longestDecomposition(text.substr(i, n - (i<<1)));
            }
        }
        // 如果一个都不相等就返回1，相当于不分段
        return n > 0 ? 1 : 0;
    }
};

有时候贪心算法解决一些困难问题非常好用，后面我们会专门总结贪心算法。

统计不同回文子序列

给定一个字符串 s，返回 s 中不同的非空「回文子序列」个数。

通过从 s 中删除 0 个或多个字符来获得子序列。

字符串仅包含 'a', 'b', 'c' 或 'd' 。

注意：结果可能很大，你需要对 $10^9 + 7$ 取模。

这道题非常困难，有余力可以参照官方题解去理解。

2 其他区间动态规划问题

除了回文串之外，区间动态规划还有许多经典问题，通过这些题目可以掌握另一种状态转移形式。

戳气球

有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

这是一道经典的区间动态规划问题，且状态转移依赖区间内的 O(n) 个子问题，上面的回文系列中都是依赖 O(1) 个子问题。这道题的状态转移思路就是这类依赖 O(n) 个子问题的常规思路，一定要完全理解。

当然这道题最难的部分不是动态规划，而是问题转化，很多困难的题目都是这样，题目本身不难，只是我们想不到把问题转化为好解决的形式，因此只能多做多积累。

我们按照正常的动态规划思路去做会发现，这道题不满足无后效性，因为每次戳破一个气球，都会改变气球之间的相邻与不相邻的关系，因此我们不能按正常思路去想这个问题。官方题解的思路是不要去想每次戳破一个气球，而是要思考每次往区间内添加一个气球，直到把区间填满所能获得的最大分数，这和每次戳破一个气球是等价的。可能这比较抽象，不太容易想明白为什么戳破和添加是等价的。

另一种理解方法是对于每一个区间 [i, j] 我们先考虑最后戳破哪个气球 k，而不是先戳破哪个气球，这样一来区间 [i , j] 所能获得的最大分数就是 nums[i] * nums[k] * nums[j] 加上之前戳破的气球的分数总和，那么之前戳破的气球的分数总和怎么计算呢？气球 k 把区间 [i, j] 分成了两个子区间 [i ,k] 和 [k, j]，在这两个区间中用同样的方法计算最后戳破哪个气球，最终得到的结果就是整个区间 [i ,j] 能获得的最大分数。

按照上面的思路，我们自然想到递归，枚举每一个 k，然后递归地计算 [i ,k] 和 [k, j]，为了避免重复计算，可以把递归过程中的结果存起来，以减少时间复杂度，这也是递归的常规优化思路，同时为了方便计算，我们可以把左右边界的数值为 1 的气球加上，重新构造一个数组 val 来存放气球，并且子区间都为开区间：

class Solution {
public:
    vector<vector<int>> rec;
    vector<int> val;

public:
    int solve(int left, int right) {
        if (left >= right - 1) {
            return 0;
        }
        if (rec[left][right] != -1) {
            return rec[left][right];
        }
        for (int i = left + 1; i < right; i++) {
            int sum = val[left] * val[i] * val[right];
            sum += solve(left, i) + solve(i, right);
            rec[left][right] = max(rec[left][right], sum);
        }
        return rec[left][right];
    }

    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        val.resize(n + 2);
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }
        val[0] = val[n + 1] = 1;
        rec.resize(n + 2, vector<int>(n + 2, -1));
        return solve(0, n + 1);
    }
};

当然这并不是动态规划，而是类似于深搜的记忆化搜索，动态规划怎么做呢？记忆化搜索是从整个区间开始自顶向下的递归计算，那我们从最小的区间开始自底向上计算，最终得到最大区间的结果，这不就是动态规划的形式吗，因此我们可以按照区间动态规划的一般遍历方法，从后向前遍历每一个位置，对每一个位置再遍历不同长度的子区间，相当于找到一个子问题，对于每个子区间就可以枚举分界点 k 进行计算，因此状态转移方程可以写出：

1	dp[i][j] = val[i] * val[k] * val[j] + dp[i][k] + dp[k][j]

边界条件是如果 i >= j 说明区间内没有气球（因为区间为开区间），能得到的最大分数为 0 。

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<int> val(n + 2);
        val[0] = val[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }
        vector<vector<int>> dp(n + 2, vector<int>(n + 2));
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 2; j <= n + 1; j++) {
                for (int k = i + 1; k < j; k++) {
                    int sum = val[i] * val[k] * val[j];
                    sum += dp[i][k] + dp[k][j];
                    dp[i][j] = max(dp[i][j], sum);
                }
            }
        }
        return dp[0][n + 1];
    }
};

多边形三角剖分的最低得分

你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是第 i 个顶点的值（顺时针顺序）。

假设将多边形剖分为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。

返回多边形进行三角剖分后可以得到的最低分。

这是上面题目的简化版，是一个典型的模板题目，给定的数组是多边形顺时针的顶点，因此对于一个区间 [i , j] 存储的是从顶点 i 到顶点 j 顺时针遍历的每一个中间顶点，我们可以遍历每一个中间顶点，这样连接顶点 i 和 k，k 和 j，这样多边形就会被分为三个部分，如下图：

一部分是区间 [i, k] 表示的多边形，一部分是区间 [k, j] 表示的多边形，一部分是三角形 ikj，这三部分的分数和最小的就是当前区间 [i, j] 的答案。

因为至少要有一个三角形，因此区间长度至少为 3 ，小于 3 的区间得分都是 0 ，这也是动态规划的边界条件。

class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        int n = values.size();
        vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
        for(int i = 0; i < n - 1; ++i)
        {
            dp[i][i+1] = 0;
        }
        for(int len = 3; len <= n; ++len)
        {
            for(int i = 0; i + len - 1 < n; ++i)
            {
                int j = i + len - 1;
                for(int k = i + 1; k < j; ++k)
                {
                    int tmp = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
                    dp[i][j] = min(dp[i][j], tmp);
                }
            }
        }
        return dp[0][n-1];
    }
};

奇怪的打印机

有台奇怪的打印机有以下两个特殊要求：

打印机每次只能打印由同一个字符组成的序列。

每次可以在从起始到结束的任意位置打印新字符，并且会覆盖掉原来已有的字符。

给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

这也是一个经典的区间动态规划模板题，打印区间 [i, j] 时如果 s[i] == s[j]，则不需要考虑 s[j] ，因为打印 s[i] 时可以顺便打印 s[j] ，所以此时 dp[i][j] = dp[i][j-1]，如果二者不相等，则要分别打印，这时枚举中间位置 k ，考虑两个区间分别打印的最小次数之和即可，即 dp[i][j] = min(dp[i][k] + dp[k+1][j])，其中 k 是 i 和 j 的是中间位置。

边界条件是 dp[i][i] = 1，一个字母需要单独打印一次。

class Solution {
public:
    int strangePrinter(string s) {
        int n = s.length();
        vector<vector<int>> f(n, vector<int>(n, INT_MAX));
        for (int i = n - 1; i >= 0; i--) {
            f[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j]) {
                    f[i][j] = f[i][j - 1];
                } else {
                    for (int k = i; k < j; k++) {
                        f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
                    }
                }
            }
        }
        return f[0][n - 1];
    }
};

预测赢家

给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。

玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。

如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。

这是一个很有意思的区间动态规划问题，当然也可以用递归的思路做，但会存在大量重复计算，因此动态规划更好，定义 $dp[i][j]$ 为在区间 nums[i … j] 上两人分数的最大差值，状态转移就是两种情况：

当前玩家拿 nums[i]，此时 dp[i][j] = nums[i] - dp[i+1][j]
当前玩家拿 nums[j]，此时 dp[i][j] = nums[j] - dp[i][j-1]

因为每次玩家都选择最优情况，因此 dp[i][j] 取二者中较大值。

边界条件是对于只有一个数字的区间就只能拿这个数字，因此 dp[i][i] = nums[i]，其他 i > j 的区间都为 0 .

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        auto dp = vector<vector<int>> (n, vector<int>(n));
        for (int i = 0; i < n; i++) {
            dp[i][i] = nums[i];
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1] >= 0;
    }
};

显然可以优化空间，改为一维数组：

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        auto dp = vector<int>(n);
        for (int i = 0; i < n; i++) {
            dp[i] = nums[i];
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1]);
            }
        }
        return dp[n - 1] >= 0;
    }
};

石子游戏

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有正整数颗石子，数目为 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。

Alice 和 Bob 轮流进行，Alice 先开始。每回合，玩家从行的开始或结束处取走整堆石头。这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。

假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。

这是上一题的一种特殊情况，数组长度为偶数且总分为奇数，因此自然可以用上一题的方法解决，当然通过数学推导也可以得出这种情况下先手玩家总能获胜，因此可以直接返回 true。

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        return true;
    }
};

编码最短长度的字符串

给定一个非空字符串，将其编码为具有最短长度的字符串。

编码规则是：k[encoded_string]，其中在方括号 encoded_string 中的内容重复 k 次。

注：

k 为正整数

如果编码的过程不能使字符串缩短，则不要对其进行编码。如果有多种编码方式，返回任意一种即可。

这是一道非常新颖的区间动态规划问题，状态定义是不容易想到的，值得反复琢磨。

这道题最难的地方不是在动态规划，而是如何找到字符串中的连续重复子串，这是另一道题重复的子字符串中讨论的问题，可以使用暴力法，也可以使用 KMP 算法，最简单的方法是使用一行代码 (s + s).find(s, 1)，关于这个方法的解释和正确性证明，可以查看重复子字符串的官方题解，总之我们可以得到 p = (s + s).find(s, 1)，也就是将两个字符串拼接起来从 1 的位置开始查找原本的字符串第一次出现的位置，如果 p >= s.size() 说明没有重复子字符串，否则存在重复子字符串，且连续重复子串是 s.substr(0, p-1)，重复次数为 s.size() / p。

比如：

s = ”aabcaabc” 
则 s + s = “aabcaabcaabcaabc”
p = (s + s).find(s, 1) = 4
因此连续重复子串是 s.substr(0, 4 - 1) = ”aabc”，重复次数为 8 / 4 = 2 次。

利用这个性质我们可以定义状态 dp[i][j] 表示子字符串 s.substr(i, j) 的最短编码串，对于长度小于 5 的子字符串，无需编码，因此长度小于 5 的区间的状态 dp[i][j] 就等于这个子字符串，长度大于 5 时，最短编码串有两种情况：

找到最小重复子串，然后进行编码
枚举区间内的分界点 k ，取两个子区间 [i, k] 和 [k+1, j] 的最短编码串长度总和最小的情况

class Solution {
public:
    string encode(string s) {
        vector<vector<string>> dp(s.size(), vector<string>(s.size(), ""));
        for(int len = 1;len <= s.size(); ++len){
            for(int i=0 ; i + len - 1 < s.size(); ++i){
                int j = i + len - 1;
                dp[i][j] = s.substr(i, len);
                if(len >= 5)
                {
                    int p = (dp[i][j] + dp[i][j]).find(dp[i][j], 1);
                    if(p < len)
                    {
                        dp[i][j] = to_string(dp[i][j].size() / p) + "[" + dp[i][i+p-1] + "]";
                    }
                    for(int k = i; k < j; ++k)
                    {
                        if(dp[i][k].size() + dp[k+1][j].size() < dp[i][j].size())
                        {
                            dp[i][j] = dp[i][k] + dp[k+1][j];
                        }
                    }
                }
            }
        }
        return dp[0][s.size()-1];
    }
};

合并石头的最低成本

有 N 堆石头排成一排，第 i 堆中有 stones[i] 块石头。

每次移动（move）需要将连续的 K 堆石头合并为一堆，而这个移动的成本为这 K 堆石头的总数。

找出把所有石头合并成一堆的最低成本。如果不可能，返回 -1 。

这是一道比较困难的题目，但思路还是比较容易理解的，具体思路和优化过程可以看题解。

移除盒子

给出一些不同颜色的盒子 boxes ，盒子的颜色由不同的正数表示。

你将经过若干轮操作去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k * k 个积分。

返回你能获得的最大积分和。

这是一个更加复杂的问题，在区间的基础上还要增加一个额外维度 k 来记录消掉区间右边连续的 k 个数字，具体思路和代码参考官方题解。