(区间dp) 力扣区间dp 题集记录

天赐细莲

4652

2022.09.18

2024.02.03

发布于未知归属地

动态规划 C++区间dp 学习分享

前言
题单
END

前言

经典例题：(区间dp) (经典例题) 石子合并

本篇博客不从0讲解，但是讲了石子合并的很多细节与理解

楼主深刻感到自己动归的水平太差

痛定思痛，决定爆刷一些dp的题

因此在力扣上搜集了一些区间dp的题练习下，以本文作为记录

注意：本文不适合连一点区间dp概念的小白观看，且不会写过多文字作题解，一些尽在代码中

小白可以先把我上面那篇博客学完了再来练习本文的题集

🔖注意点

推荐把数据范围定在[1, n]

然后区间dp的范围开到[0, n + 1]

这样就可以避免一些题出现的越界和边界特判问题

🔖思路与技巧

一个重要思路是，我们要处理一个长度为len的区间时，则可以优先考虑len和len-1的关系

为什么是len-1，因为区间dp通常是len++来处理的，也就是步长为1的单位递增处理

如果是len-2,len-3那这个步长是不是没必要是1，反之表明len-1这个状态即为重要

重点思考两侧点的关系，单个侧边点链接后构成短len的关系

有时可以用二叉树的思维去思考区间dp，见1130. 叶值的最小代价生成树

🔖碎碎念

很多回文串的题都和区间dp有点

有些题目会发现用记忆化dfs写方便很多

比赛可以写dfs，但作为练习的话还是多写写dp，虽然想到一个另一个也会比较好写

区间dp可以理解为线性dp一种特殊表达形式，而线性dp懂的都懂

题单

🏷️5. 最长回文子串

⭐⭐经典例题

题意与思路

如题名，求最长回文字串

注意长度为2的需要特判

其他解法：马拉车算法

Code

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        s = ' ' + s;
        vector<vector<bool>> dp(n+1, vector<bool>(n+1));
        for (int i = 0; i <= n; i++) {
            dp[i][i] = true;
        }

        int start = 1;
        int L = 1;
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                if (s[i] == s[j] && (dp[i+1][j-1] || len == 2)) {
                    dp[i][j] = true;
                    start = i;
                    L = len;
                }
            }
        }

        return s.substr(start, L);
    }
};

🏷️87. 扰乱字符串

⭐两个串分别定义区间 2*2 = 4维

题意与思路

两个串，现有一种操作

若 len(s) <= 1 停止
可以将 s = x + y 变为 s = y + x

能否通过这个操作，将串1变为串2

其实这道题用dfs暴力记忆化很方便

下面主要说一下区间dp的思路，本题的难点在于如何确定状态

通常的字符串区间dp都是定义单个串s，dp[i][j]表示在区间[i, j]处于一种则怎样的状态

而本题的两个串，很直观的想法是s1[i, j]和s2[i, j] 可以通过操作判断bool

因此大胆的定义四维dp[i1][j1][i2][j2]

又因为长度不同的串，必然不同。因此可以用一个维度表示长度，两个维度表示两个串的首位(或者尾位)，从而压缩到三维。但是本质要从四维的角度进行分析

而状态转移则是很明显的题目中给出的操作

Code

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1.size() != s2.size()) {
            return false;
        }
        int n = s1.size();

        // 本质是一个四维dp[i1][j1][i2][j2]
        // s1[i1, j1] ?= s2[i2, j2]
        // 由于长度相同，则压缩 dp[i][j][len] => dp[i1][i1+len-1][j][j+len-1]
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(n + 1)));

        // 初始化长度为1
        for (int i = 0; i < n; i += 1) {
            for (int j = 0; j < n; j += 1) {
                dp[i][j][1] = s1[i] == s2[j];
            }
        }

        for (int len = 2; len <= n; len += 1) {
            for (int i = 0; i + len - 1 < n; i += 1) {
                for (int j = 0; j + len - 1 < n; j += 1) {
                    // 分割len
                    for (int k = 1; k < len; k += 1) {
                        dp[i][j][len] |= 
                            // 不交换
                            (dp[i][j][k] && dp[i + k][j + k][len - k]) || 
                            // 交换
                            (dp[i][j + len - k][k] && dp[i + k][j][len - k]) ;
                    }
                }
            }
        }

        return dp[0][0][n];
    }
};

🏷️312. 戳气球

⭐Dire Wolf

hdu5115: Dire Wolf（一个壳子）

题意与思路

每次戳破一个气球，两侧的气球会提供一个辅助值

戳破的气球会消失，即原来左右两侧的并未相邻的

和hdu5115可以说完全一致，该题是2014ACM/ICPC亚洲区北京站真题

详细讲解见上方博客链接

Code

// 类似的题：https://acm.hdu.edu.cn/showproblem.php?pid=5115 Dire Wolf
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        // 化为[0, n+1]实际操作[1, n]
        // 分别首端尾端添加哨兵
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        // [i, j]获得的最大价值，则初始化为0
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));

        // 添加了哨兵和预留空间可以从len=1开始
        for (int len = 1; len <= n; len += 1) {
            for (int i = 1, j = i + len - 1; j <= n; i += 1, j += 1) {
                // 石子合并变体[i, j]所有点都处理
                // 分为三块区域[i, k-1] [k] [k+1, j]
                for (int k = i; k <= j; k += 1) {
                    dp[i][j] = max(dp[i][j], 
                                dp[i][k - 1] + dp[k + 1][j] +   // 两边的dp
                                nums[k] *                       // k点的点权
                                nums[i - 1] * nums[j + 1]);     // 区间外两侧
                }
            }
        }

        return dp[1][n];
    }
};

🏷️375. 猜数字大小 II

⭐靠两次比较来松弛

题意与思路

由代价的猜数字游戏，代价就是每次猜错的数字

问对于[1, n]中的每个数字，保证最小的代价是多少

非常典型的划分为 [i, k-1] [k] [k + 1][j] 分为三部分

两次不同的判断为了一次松弛

int maxSide = max(dp[i][k - 1], dp[k + 1][j]);
dp[i][j] = min(dp[i][j], maxSide + k);

Code

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        // 不合法状态归零
        // 合法状态INF
        // len = 1不用取为0
        for (int i = 0; i <= n; i += 1) {
            for (int j = 0; j < i; j += 1) {
                dp[i][j] = 0;
            }
            dp[i][i] = 0;
            for (int j = i + 1; j <= n; j += 1) {
                dp[i][j] = 0x3f3f3f3f;
            }
        }

        for (int len = 2; len <= n; len += 1) {
            for (int i = 1, j = i + len - 1; j <= n; i += 1, j += 1) {
                for (int k = i; k < j; k += 1) {
                    // 分为三部分 [i, k-1] [k] [k + 1][j]
                    // 两边保证都取到，考虑较大的
                    int maxSide = max(dp[i][k - 1], dp[k + 1][j]);
                    // 累计上当前的k,真正的松弛
                    dp[i][j] = min(dp[i][j], maxSide + k);
                }
            }
        }

        return dp[1][n];
    }
};

🏷️486. 预测赢家

⭐博弈类区间dp

题意与思路

两人玩取数游戏，两人轮流取数，只能从首段或者末端取，比谁取值最后最大

这里的定义又非常巧妙，定义的是 当前选手的差值 包含的博弈的思想

Code

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        // 添加哨兵，化区间为[1, n]
        nums.insert(nums.begin(), 0);

        // 当前玩家区间[i, j]，与另一位玩家的差值
        // 注意：当前玩家不一定是先手，博弈基本概念
        vector<vector<int>> dp(n + 2, vector<int>(n + 2));

        // // 一个区间，拿了直接结束，差值就是nums[i]
        // for (int i = 1; i <= n; i += 1) {
        //     dp[i][i] = nums[i];
        // }

        // len从1开始dp，体现了数组长度的开辟技巧
        // dp[n+2][n+2] [0, n+1] (存在0和n+1的预留位置)
        for (int len = 1; len <= n; len += 1) {
            for (int i = 1, j = i + len - 1; j <= n; i += 1, j += 1) {
                // 拿取左边，则减去前一个len-1的对手的状态
                int left = nums[i] - dp[i + 1][j];
                // 拿取右边，则减去前一个len-1的对手的状态
                int right = nums[j] - dp[i][j - 1];
                dp[i][j] = max(left, right);
            }
        }

        // 对于整个区间最开始的当前选手就是先手
        return dp[1][n] >= 0;
    }
};

🏷️516. 最长回文子序列

⭐经典例题

题意与思路

经典例题

两边相同 dp[len-2] + 2
两边不同选取一边 max(dp[len-1])

Code

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        s = ' ' + s;

        vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        for (int i = 1; i <= n; i += 1) {
            dp[i][i] = 1;
        }

        for (int len = 2; len <= n; len += 1) {
            for (int i = 1, j = len; j <= n; i += 1, j += 1) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[1][n];
    }
};

🏷️546. 移除盒子

💀区间dp中的战斗机 / 没有写，留个坑

🏷️647. 回文子串

⭐统计回文字串数量

题意与思路

统计回文字串数量

其实完全可以一遍判断回文串，一遍计数

但这里给出另一种方式，就是求方案数的常见累计法

Code

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        s = ' ' + s;

        vector<vector<bool>> is(n+1, vector<bool>(n+1));
        for (int i = 0; i <= n; i++) {
            is[i][i] = true;
        }
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                if (s[i] == s[j] && (is[i+1][j-1] || len == 2)) {
                    is[i][j] = true;
                }
            }
        }

        // 定义dp为区间为[i, j]的回文子串数目
        vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        // 长度为1的区间
        for (int i = 1; i <= n; i += 1) {
            dp[i][i] = 1;
        }
        // 长度为2的区间
        for (int i = 1; i <= n - 1; i += 1) {
            dp[i][i + 1] = (s[i] == s[i + 1]) ? 3 : 2;
        }

        // 从长度为3的区间开始dp
        for (int len = 3; len <= n; len += 1) {
            for (int i = 1, j = len; j <= n; i += 1, j += 1) {
                // 叠加区间的左右len-1的数量
                // 并减去重复的区间[i+1, j-1]
                dp[i][j] += dp[i + 1][j];
                dp[i][j] += dp[i][j - 1];
                dp[i][j] -= dp[i + 1][j - 1];
                // 特殊情况，两边字符相等，且中间是回文串，则+1
                // 预处理区间是否为回文
                if (s[i] == s[j] && is[i + 1][j - 1]) {
                    dp[i][j] += 1;
                }
            }
        }

        return dp[1][n];
    }
};

🏷️664. 奇怪的打印机

⭐字符串和石子合并混合

题意与思路

每次只能在任意区间内写一个字符，可以覆盖之前的

求获得目标串的次数

Code

class Solution {
public:
    int strangePrinter(string s) {
        int n = s.size();
        s = ' ' + s;
        // 求最小，初始无穷大
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0x3f3f3f3f));
        // 单个位置只要一次
        for (int i = 1; i <= n; i += 1) {
            dp[i][i] = 1;
        }

        for (int len = 2; len <= n; len += 1) {
            for (int i = 1, j = i + len - 1; j <= n; i += 1, j += 1) {
                if (s[i] == s[j]) {
                    // 类似字符串类的区间dp
                    // 从len-1中取最小
                    dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]);
                } else {
                    // 类似石子合并
                    // 找分割点松弛
                    for (int k = i; k <= j; k += 1) {
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }

        return dp[1][n];
    }
};

🏷️678. 有效的括号字符串

⭐括号串平衡

题意与思路

给定一个只包含三种字符的字符串：（，）和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串。

整体平衡问题，非常适合使用区间dp

括号串是怎么平衡的，大致分为两类

(()) 包住内部平衡
()() 相邻的区间平衡

Code

class Solution {
public:
    bool checkValidString(string s) {
        auto check = [&](int l, int r) {
            return (s[l] == '(' || s[l] == '*') && (s[r] == ')' || s[r] == '*');
        };
        int n = s.size();
        // dp[i][j] [i,j]是否合法
        bool dp[n][n];
        memset(dp, false, sizeof(dp));
        
        // 初始化长度1和长度2的情况
        for (int i = 0; i < n; i += 1) {
            dp[i][i] = s[i] == '*' ? true : false;
        }
        for (int i = 1; i < n; i += 1) {
            dp[i - 1][i] = check(i - 1, i);
        }

        for (int len = 3; len <= n; len += 1) {
            for (int l = 0, r = l + len - 1; r < n; l += 1, r += 1) {
                // 最外两个配对，则由内层直接扩展
                if (check(l, r)) {
                    dp[l][r] = dp[l + 1][r - 1];
                }
                // 分割成两部分，两部分合格，则整体合格
                for (int k = l; k < r && !dp[l][r]; k += 1) {
                    dp[l][r] |= dp[l][k] && dp[k + 1][r];
                }
            }
        }

        return dp[0][n - 1];
    }
};

🏷️730. 统计不同回文子序列

⭐计数与判重

题意与思路

统计不同回文子序列

相同的只计一次

Code

三维

考虑每个字符，假设该区间是以某字符为结尾的状态

其实这个三维的解法反而不怎么常见

class Solution {
public:
    const int mod = 1e9 + 7;
    int countPalindromicSubsequences(string s) {
        int n = s.size();
        // 本题只有abcd4个字符
        // dp[ch][i][j] 当前[i, j]的区间，是ch字符的不同回文子序列数量
        vector<vector<vector<long>>> dp(4, vector<vector<long>>(n, vector<long>(n)));

        // len = 1
        for (int i = 0; i < n; i += 1) {
            dp[s[i] - 'a'][i][i] = 1;
        }

        for (int len = 2; len <= n; len += 1) {
            for (int i = 0, j = len - 1; j < n; i += 1, j += 1) {
                // 考虑每个字符，目的是考虑每种可能性
                for (char k = 0, ch = 'a'; k < 4; k += 1, ch += 1) {
                    // 这里是判断两个字符与ch是否相等
                    // 不是直接s[i] == s[j]
                    // 累计中间的全部 + 2
                    //  +2 的理解：
                    //      新添加了x和xx
                    //      原来的x和xx变为了xxx和xxxx
                    if (s[i] == ch && s[j] == ch) {
                        dp[k][i][j] = (dp[0][i+1][j-1] + dp[1][i+1][j-1] + dp[2][i+1][j-1] + dp[3][i+1][j-1] + 2) % mod;
                    }
                    // 左右边界考虑单个字符，必须要更新到
                    // 保留同一个字符的len-1的区间
                    else if (s[i] == ch && s[j] != ch) {
                        dp[k][i][j] = dp[k][i][j-1];
                    }
                    else if (s[i] != ch && s[j] == ch) {
                        dp[k][i][j] = dp[k][i+1][j];
                    }
                    // 完全不搭边的字符，保留len-2的区间
                    else {
                        dp[k][i][j] = dp[k][i+1][j-1];
                    }
                }
            }
        }

        long ans = 0;
        for (int i = 0; i < 4; i += 1) {
            ans = (ans + dp[i][0][n - 1]) % mod;
        }

        return ans;
    }
};

二维

常规的状态累计和去重解法，应该要掌握

class Solution {
public:
    const int mod = 1e9 + 7;
    int countPalindromicSubsequences(string s) {
        int n = s.size();

        // 预处理对于当前字符，前面和后面出现的位置
        vector<int> idx = vector<int>(4, -1);
        vector<int> pre(n, -1);
        for (int i = 0; i < n; i += 1) {
            pre[i] = idx[s[i] - 'a'];
            idx[s[i] - 'a'] = i;
        }
        idx = vector<int>(4, n);
        vector<int> nex(n, n);
        for (int i = n-1; i >= 0; i += -1) {
            nex[i] = idx[s[i] - 'a'];
            idx[s[i] - 'a'] = i;
        }

        // [i, j]区间，不同的回文字串数量
        vector<vector<long>> dp(n, vector<long>(n));
        for (int i = 0; i < n; i += 1) {
            dp[i][i] = 1;
        }

        for (int len = 2; len <= n; len += 1) {
            for (int i = 0, j = i + len - 1; j < n; i += 1, j += 1) {
                // 相同，分类讨论
                if (s[i] == s[j]) {
                    // 搜索内部是否有相同字符的子区间
                    int left = nex[i], right = pre[j];
                    // 核心思想：
                    // 原本内部的dp[i+1][j-1]再加上当前两侧的xx
                    // 则变成了xdp[i+1][j-1]x
                    // 因此应该有两倍2 * dp[i+1][j-1]
                    // 但是可能会出现x...x··x...x的情况
                    // 即中间的部分已经有x夹击成的回文串了
                    // 因此要判重
                    
                    // 只有唯一的点，加上xx
                    if (left == right) {
                        dp[i][j] = 2LL * dp[i+1][j-1] + 1;
                    }
                    // 有长度超过1的区间
                    else if (left < right) {
                        dp[i][j] = 2LL * dp[i+1][j-1] - dp[left+1][right-1];
                    }
                    // 没有相同字符，记得加上x和xx
                    else {
                        dp[i][j] = 2LL * dp[i+1][j-1] + 2;
                    }
                } 
                // 不同，累计dp[len-1]
                else {
                    dp[i][j] = 0LL + dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
                }
                dp[i][j] = (dp[i][j] + mod) % mod;
            }
        }

        return dp[0][n-1];
    }
};

🏷️1000. 合并石头的最低成本

⭐规定一次合并数量的石子合并

题意与思路

与常规石子合并((区间dp) (经典例题) 石子合并)不同的是本题是规定没测合并连续合并的石子数量

常规石子合并是合并两堆，这次规定k堆

这里二维和三维的定义都非常非常巧妙

还有有关步长的，循环，等等都非常值得品味

个人还没完全理解透该题，处于一种似懂非懂的状态

Code

三维dp

dp[i][j][k] 区间[i, j]合并成k堆的值

class Solution {
public:
    int mergeStones(vector<int>& stones, int K) {
        int n = stones.size();
        // 最后一次必然拿走k个,之前每次拿走k-1个
        if ((n - 1) % (K - 1) != 0) {
            return -1;
        }
        // dp[i][j][k] 区间[i, j]合并成k堆
        // 下标定到 [1, n]
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 1, vector<int>(K + 1, 0x3f3f3f3f)));

        vector<int> pre(n + 1);
        for (int i = 1; i <= n; i += 1) {
            // 常规石子合并的前缀和计算
            pre[i] = pre[i - 1] + stones[i - 1];
            // 长度为1的合成一堆不需要花费
            dp[i][i][1] = 0;
        }

        // - K堆合并成一堆，dp[1] = dp[K] + sum
        // - K可分解成m堆+k-m堆
        //   归纳总结后发现(m, k-m)等价于(1, k-1)

        for (int len = 2; len <= n; len += 1) {
            for (int i = 1, j = i + len - 1; j <= n; i += 1, j += 1) {
                // 合并成k堆需要的值
                // 松弛第三维
                for (int k = 2; k <= K; k += 1) {
                    for (int m = i; m < j; m += 1 {
                        // 由1堆和k-1堆合并成k堆
                        dp[i][j][k] = min(dp[i][j][k], dp[i][m][1] + dp[m + 1][j][k - 1]);
                    }
                }
                // 处理完[i, j]的各种堆数后
                // K堆石子一下子合并成1堆
                dp[i][j][1] = dp[i][j][K] + pre[j] - pre[i - 1];
            }
        }

        // [1, n]合成一堆的价值
        return dp[1][n][1];
    }
};

二维

class Solution {
public:
    int mergeStones(vector<int>& stones, int K) {
        int n = stones.size();
        // 最后一次必然拿走k个,之前每次拿走k-1个
        if ((n - 1) % (K - 1) != 0) {
            return -1;
        }
        // dp[i][j] 区间[i, j]尽可能合并的最小价值
        // 下标定到 [1, n]
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0x3f3f3f3f));

        vector<int> pre(n + 1);
        for (int i = 1; i <= n; i += 1) {
            // 常规石子合并的前缀和计算
            pre[i] = pre[i - 1] + stones[i - 1];
            // 长度为1的合成一堆不需要花费
            dp[i][i] = 0;
        }

        // - 该长度是否能合并成1堆，则+sum
        // - 分割点的步长

        for (int len = 2; len <= n; len += 1) {
            for (int i = 1, j = i + len - 1; j <= n; i += 1, j += 1) {
                // 注意步长是K-1，个人还不能太好解释
                // 可以类比为单调队列优化多重背包的分组
                // 只有同样能抵消的状态才一起松弛
                for (int m = i; m < j; m += (K - 1)) {
                    // 这里不计sum
                    // sum只有确实可以合并的成1堆的状态才叠加
                    // 这里松弛的是理想的虚拟状态
                    dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j]);
                }
                // 判断该长度能否由K堆合并成1堆
                if ((len - 1) % (K - 1) == 0) {
                    dp[i][j] +=pre[j] - pre[i - 1];
                }
            }
        }

        // 因为一开始特判走了
        // 因此这里必然是能由K堆合并成一堆的状态
        return dp[1][n];
    }
};

🏷️1130. 叶值的最小代价生成树

⭐以二叉树的思维进行区间dp

题意与思路

给出的序列有序的做为二叉树的叶节点，每次合并有一份贡献值。

很巧妙地将有序序列的区间dp和二叉树自地向上的合并涉及到了一起。

以后做区间dp的时候可以尝试用树形结构去思考。

Code

class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        const int n = arr.size();
        
        // 区间[i, j]题目要求答案的最小值 初始化为inf
        int dp[n][n];
        // 区间[i, j]内最大的元素值       初始化为-inf
        int maxx[n][n];
        memset(maxx, -1, sizeof(maxx));
        memset(dp, 0x3f, sizeof(dp));
        // 长度为1的单独处理
        for (int i = 0; i < n; i += 1) {
            dp[i][i] = 0;
            maxx[i][i] = arr[i];
        }

        // 区间长度为2开始考虑
        for (int len = 2; len <= n; len += 1) {
            for (int i = 0, j = i + len - 1; j < n; i += 1, j += 1) {
                // 维护len长度的区间最值，贡献到后续的遍历中
                maxx[i][j] = max(maxx[i][j - 1], arr[j]);
                // k划分的区间<len
                for (int k = i; k < j; k += 1) {
                    dp[i][j] = min(dp[i][j], 
                        dp[i][k] + dp[k + 1][j] + 
                        maxx[i][k] * maxx[k + 1][j]
                        );
                }
            }
        }

        return dp[0][n - 1];
    }
};

🏷️1039. 多边形三角剖分的最低得分

⭐几何分割凸多边形

题意与思路

有n个点的凸多边形要求分割成n-2个三角形

初看时一道计算几何的问题

但还是用区间dp来处理，大问题由小问题构成

确定区间两侧，枚举中间的分割点来松弛子问题

Code

class Solution {
public:
    // 注意：本题不要陷入n个点分为n-2个三角形这个点上
    // 还是按照大问题由子问题构成处理
    int minScoreTriangulation(vector<int>& values) {
        int n = values.size();
        // 个人习惯，化下标为[1, n]
        values.insert(values.begin(), 0);
        // 问什么设什么，区间[i, j]长度len构成len-2个▲的价值
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));

        // 只少三个点构成三角形
        for (int len = 3; len <= n; len += 1) {
            for (int i = 1, j = i + len - 1; j <= n; i += 1, j += 1) {
                // < len-3为0
                // >=len-3为INF
                dp[i][j] = 0x3f3f3f3f;
                
                // k这个点是两块区域共用的
                // 理解为k向i，j各连一条线
                // 将区间划分为[i, k] [k, j] 两个部分
                // 而[i, k] [k, j]都是已经处理的子问题
                for (int k = i + 1; k < j; k += 1) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]);
                }
            }
        }

        return dp[1][n];
    }
};

🏷️1143. 最长公共子序列

⭐⭐经典例题

题意与思路

其实本题不是区间dp，但也是一个经典的字符串dp

将两个字符串写成一行一列，看成一个二维矩阵找转移

Code

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size();
        int m = text2.size();
        // 添加哨兵，便于dp的边界操作
        string s = ' ' + text1;
        string t = ' ' + text2;
        // i为s的每一个字符，j为t的每一个字符
        // 第i个字符到第j个字符可以匹配的长度
        vector<vector<int>> dp(n+1, vector<int>(m+1));

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s[i] == t[j]) {
                    // 有相等的，可以从两个串一起往前一个字符+1
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    // 没有相等的，要么追随当前层前一位置，要么追随上一层的该位置
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        // 末尾全匹配完，最大的dp
        return dp[n][m];
    }
};

🏷️1312. 让字符串成为回文串的最少插入次数

⭐考虑哪一边操作

题意与思路

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

思路1 反其道而行之 len - 最长回文系列
思路2 正向思考 ↓code

Code

class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        // 区间[i, j]成为回文串需要插入的字符数字
        vector<vector<int>> dp(n, vector<int>(n));
        // 长度为1的本身就是回文串，插入次数为0
        for (int len = 2; len <= n; len += 1) {
            for (int i = 0, j = i + len - 1; j < n; i += 1, j += 1) {
                // 相同则不用插入，内部的值覆盖
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1];
                } 
                // 不同则考虑配对哪一边
                else {
                    dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;;
                }
            }
        }
        return dp[0][n-1];
    }
};

🏷️1547. 切棍子的最小成本

⭐学会将选择顺序问题转化为区间dp问题

题意与思路

提供一些分割点来分割，求最低值

虽然看似是有顺序决定的，但是dp就是一种获得最优质的解法

又是一道根据k点划分区域的题

Code

class Solution {
public:
    int minCost(int n, vector<int>& cuts) {
        int m = cuts.size();
        vector<vector<int>> dp(m + 2, vector<int>(m + 2));

        sort(cuts.begin(), cuts.end());
        // 前后添加空位哨兵
        cuts.insert(cuts.begin(), 0);
        cuts.push_back(n);

        // 为什么长度为1时val不是n呢？
        // 因为这里不是说第一次切，而是取单个点的时候
        // 这个点提供的最优的作用是多少
        for (int i = 1; i <= m; i += 1) {
            // dp[i][i] = n;
            dp[i][i] = cuts[i + 1] - cuts[i - 1];
        }

        // 区间dp模板
        for (int len = 2; len <= m; len += 1) {
            for (int i = 1, j = i + len - 1; j <= m; i += 1, j += 1) {
                // 先假设是一个无穷值，不断寻求获得最小的可能
                dp[i][j] = 0x3f3f3f3f;
                for (int k = i; k <= j; k += 1) {
                    // 不考虑中间的细节状态，看作一个整体
                    // 因为加了哨兵和预留了空间，因此i-1和i+1不会越界
                    dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + cuts[j + 1] - cuts[i - 1]);
                }

            }
        }

        return dp[1][m];
    }
};

🏷️1690. 石子游戏 VII

⭐博弈的轮替特点

题意与思路

博弈取石子游戏。

只能取序列的两端，获得的权值是剩余石头的数值和。即剔左右拿中间（的权值）

Alice&Bob足够聪明，求到最后Alice的差值最大化

典型的博弈问题，但不是问谁赢，因为这里根据题意Bob必输。

从取石子的特点来看，典型的区间dp问题，大区间 = max(小区间)贡献得来。

而转移的dp是上一轮的另一位选手的值，根据博弈的特点，对手与自身的收益互逆的，因此贡献为-dp[上一轮]

由于本题的特点，只拿两端之一，没有另外的分割点，因此没有常见的第三重循环，当然这个1e3的数据量也不允许O(n^3)的算法。当然核心还是理解题意。

Code

class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        const int n = stones.size();

        // 预处理前缀和
        vector<int> pre(n + 1);
        for (int i = 1; i <= n; i += 1) {
            pre[i] = pre[i - 1] + stones[i - 1];
        }

        // 区间dp [0, n + 1] (有效区间->) [1, n]
        // dp[i][j] => [i, j] 两者的差值
        vector<vector<int>> dp(n + 2, vector<int>(n + 2));
        for (int len = 1; len <= n; len += 1) {
            for (int i = 1, j = i + len - 1; j <= n; i += 1, j += 1) {
                // [i, j] 本题的val是sum[range]
                // i, sum[i + 1, j]
                // sum[i, j - 1], j 
                // Alice&Bob (轮换交替->) 负的上一轮的dp
                dp[i][j] = max( -dp[i + 1][j] + (pre[j] - pre[i]),
                                -dp[i][j - 1] + (pre[j - 1] - pre[i - 1])
                            );
            }
        }

        return dp[1][n];
    }
};

🏷️2312. 卖木头块

⭐分别考虑横纵分割点

题意与思路

已知一堆小矩形的价值，如何分割大矩形使得价值最大

行列分别找分割点做松弛，就是多维度更新

Code

class Solution {
public:
    long long sellingWood(int m, int n, vector<vector<int>>& prices) {
        swap(n, m);
        // 表示 i*j 大小的的块能存放的最大值
        vector<vector<long long>> dp(n+1, vector<long long>(m+1));
        // 先把能放入的直接放进去的块
        for (vector<int>& arr : prices) {
            int row = arr[0], col = arr[1], val = arr[2];
            dp[row][col] = max(dp[row][col], 1LL * val);
        }

        // 枚举所有的 i*j
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 分割行
                for (int k = 0; k <= i; k++) {
                    dp[i][j] = max(dp[i][j], dp[k][j] + dp[i-k][j]);
                }
                // 分割列
                for (int k = 0; k <= j; k++) {
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j-k]);
                }
            }
        }

        return dp[n][m];
    }
};

前言

🔖注意点

🔖思路与技巧

🔖碎碎念

题单

🏷️5. 最长回文子串

⭐⭐经典例题

题意与思路

Code

⭐两个串分别定义区间 2*2 = 4维

题意与思路

Code

⭐Dire Wolf

题意与思路

Code

⭐靠两次比较来松弛

题意与思路

Code

⭐博弈类区间dp

题意与思路

Code

⭐经典例题

题意与思路

Code

💀区间dp中的战斗机 / 没有写，留个坑

⭐统计回文字串数量

题意与思路

Code

⭐字符串和石子合并混合

题意与思路

Code

⭐括号串平衡

题意与思路

Code

⭐计数与判重

题意与思路

Code

⭐规定一次合并数量的石子合并

题意与思路

Code

⭐以二叉树的思维进行区间dp

题意与思路

Code

⭐几何分割凸多边形

题意与思路

Code

⭐⭐经典例题

题意与思路

Code

⭐考虑哪一边操作

题意与思路

Code

⭐学会将选择顺序问题转化为区间dp问题

题意与思路

Code

⭐博弈的轮替特点

题意与思路

Code

⭐分别考虑横纵分割点

题意与思路

Code

END