好久不见，先报喜讯主包已经脱离了那段纠缠压抑的关系，也是最近要开始找工作了决定好好地重新拾起我对于分享和学习的热海和痴迷，今天我们继续C++进阶（机器学习短期不会更新因为那本书上有很多错误的代码和过时的函数，建议严查这本书的审核(#>д<)ﾉ）

OK，废话就说这么多，直接进入正题！

依旧叠甲：

动态规划，如果你之前有过了解你可能对他的印象是01背包、爬楼梯、买股票亦或者斐波那契数列，可动态规划究竟是什么呢？ 有时候名字本身并不重要，它是怎么运作的可能比定义更能让你理解这个名字

---

一、定义：

动态规划（DP）一种通过将复杂问题分解为相对简单的子问题来解决问题的方法。(这听起来很想分治、递归，事实上也差不太多，在编程中难学的东西特有的相似 Q.A Q. )

动态规划的核心解决问题的思路基本相同

1.找最优子结构和最小子问题

2.构建状态转移方程

3.确保无后效性（即已确定的子问题的答案不能因为之后的子问题发生改变）

（这篇量大管饱，不打算出分集，一个是因为大家学累了之后可以直接休息不用来回找，另一个原因是大家再次学习时会在翻的时候起到一个复习的效果）

---

二、分类：

从目的上来讲

1.计数型dp

2.最值型dp

3.存在性dp

从状态结构上来讲

1. 线性 DP

（1）斐波那契数列及其衍生问题（打家劫舍 I & II）

（2）最长递增子序列（LIS）

（3）最长公共子序列（LCS）（多维dp）

（4）整数拆分

2. 背包问题

（1）0-1 背包

（2）完全背包

（3）多重背包

（4）分组背包

3. 区间 DP

（1）最长回文子序列

（2）矩阵链乘法

4. 状态压缩 DP

（1）旅行商问题（TSP）

（2）最短 Hamiltonian 路径

5. 树形 DP

（1）树的直径

（2）二叉树中的最大路径和

（3）打家劫舍 III

---

三、线性DP

（1）核心思路

状态转移方程简单，难度主要体现在实现过程中对于子问题的理解

（2）斐波那契数列及其衍生问题（打家劫舍 I & II）

leetcode 70：爬楼梯

【问题】

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

【解析】

在第0个台阶即还没爬的时候，到达第1个台阶的方案只有1种 即从0到1 的一步

到第2个台阶时，方案有两个分别为 从1到2 的一步 和 从 0 到 2的二步

第3个台阶时，方案有两部分分别为 从2到3 的一步 和 从1到3 的二步【特别注意是两部分】

一部分是从2到3 这个过程，“从2”就要求我们已经到2了，到第2个台阶的方案我们已经求解出来了直接相加即可，另一部分就是从1到3，没什么好说的

据此我们不难发现这就是个稍微隐晦一点的斐波那契数列 方案数: F(n) = F(n-1) + F(n-2)（F(0)=1,F(1)=1）

---

leetcode 198: 打家劫舍I

【问题】

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

【解析】

可恶啊！！！竟然不能连着偷！！！

好吧，那么分析一下

假如我们偷了第一间那么 → 就不能偷第二间，也就是下一次偷可能会是第三间（反正不是第二间），那么我们要不要偷第三间呢？

如果偷的话 收益为 p1+p3 ，不偷的话收益就只剩p1了

！但是作为有逻辑，懂编程的小偷，如何保证偷的最多呢？肯定是max（）函数了，我们比较的第一个对象有了，第二个呢？

我们把这个过程拆成两步，第一步，如果偷第一间的话我们的最大收益（第二步，计算最大收益）就是p1+p3，如果不偷呢？第一步就是不偷p1，然后最大的收益就是p2 ，于是我们的状态转移方程即为F(i) = max(F(i-1),F(i-2)+p[i])

---

（3）最长递增子序列（LIS）

leetcode 300：

【问题】

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

例如 [9,1,2,3,4,5,0] 最长递增子序列[1,2,3,4,5] 长度为5

【解析】

这个问题从直觉上来讲暴力（即暴力枚举全部枚举出来）肯定能做，但是时间复杂度太高，如何优化呢？你可能想到用两个变量分别表示子序列的前面和后面， [9,1,2,3,1,2,3,4,5,6,1,2,3,4,9,10]这个例子中，你会发现序列的前面和后面需要变更很多次，但是绝对比暴力枚举要高效的多，这个方法叫做滑动窗口，但是在这个问题中，由于回溯（回到之前的某一步的状态）很难理想的实现，所以我们也不得不放弃这个想法。

如果用动态规划来解决的话，那么状态转移方程式是什么？与前两题不同，模拟的难度会更高，因为nums数组的情况可能差别很大，我们先随便看一个[9,1,2,3,1,2,3,4,5,6,1,2,3,4,9,10]

第一步先单看9这个数字，emm…没什么的…但就他自己的话，肯定也得算长度，所以我们推出了第一个推论：max_len的初始化以及dp数组的初始化一定为1，

然后再看数字1，9肯定比1大，我们的dp[0]记录就结束了，与此同时要更新一下max_len，第二个推论就是max_len肯定要不断更新，放在一个for里面，而且整个代码应该是两个for嵌套，

我们接下来可能希望从1开始后面的数比1大就加1，BUT！如果这样执行代码，到第一个4的时候，dp[7] = 6,这显然太夸张了，也不是我们想要的，推论三：所以在更新dp之前需要if语句的筛选，if（num[j]<num[i]）

这样的情况下，我们该如何确定状态转移方程呢？即如何得知当下的dp[i]的长度是多少呢？聪明的你应该有一点感觉了，推论四：答案就是看最近的上一个符合if条件的数字对应的dp的值是多少然后加1即可 dp[i] = max（dp[i] , dp[j]+1）

至此我们基本上已经解决了这道问题然后把这些推论组装一下，就OK了

int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) return 0;
    int n = nums.size();
    vector<int> dp(n, 1); // dp[i]表示以nums[i]结尾的LIS长度，初始为1（自身）
    int max_len = 1;

    for (int i = 1; i < n; ++i) {
        // 遍历i之前的所有元素j，寻找比nums[i]小的元素
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        max_len = max(max_len, dp[i]); // 更新全局最大值
    }
    return max_len;
}

---

（4）最长公共子序列（LCS）

leetcode 1143

【问题】

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

【分析】

可恶啊！！这道题的难度感觉更难了，其实也没那么让人难以接受就是了，因为在一维的角度上来讲从哪里下手都很棘手，绕开dp的话会有点绕，想用多维dp的话该怎么处理呢？

先来解释一个问题，我们为什么要用二维？

这个问题它很难直接的解释，如果我们描述一根线段，我们只需要告诉对方长度就可以了，其他的方面对方会自己理解，但是我们在描述一个矩形的时候，无论是只告诉长度还是只告诉宽度，亦或者只告诉对方面积都有点不够形象，于是我们需要分两次分别告诉它长和宽

如果我们只需要在乎商品的价格怎么采买不会太贵，一维dp绝对戳戳有余，但是想买的又便宜东西的品质还得尽量高用一维dp就比较困难了，我需要另开一个dp去看在花定量的钱的情况下，该如何买到品质最好的，如果你到这里能听懂，恭喜你，优先学会了我们背包问题的出题思路的核心

回到这道题本身，我们很难再想一维dp的情况下去模拟，因为会有很多的情况，但好在这些情况还是可以做一个大类的划分的，首先我们的dp[i][j]中的ij分别代表每个string里面的一个字符的位置，如果 string[i]==string[j] 我们的dp[i][j]肯定毫无疑问的加1

可问题就在不一样之后的处理，如果不一样的话，状态转移方程怎么写？ 如果是一维的情况下该等于什么就等于什么，但是这是二维，即使不符合 string i == string j 的条件 dp[i][j] 还是有可能发生变化的，因为我们的要求是最长公共子序列，也就是要在 string[i][j-1]和string[i-1][j]之间选择大的一方

 其他的套路和上题差不多所以不过度展开，我们直接进入代码展示:

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length(), n = text2.length(); // 获取两个字符串的长度
    
    // 创建二维DP数组，dp[i][j]表示text1[0..i-1]与text2[0..j-1]的LCS长度
    // 多开一行一列（索引0）作为边界条件（空字符串的情况）
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    
    // 遍历两个字符串的所有前缀
    for (int i = 1; i <= m; i++) {
        char c1 = text1.at(i - 1); // 当前text1的字符（i-1是实际索引）
        for (int j = 1; j <= n; j++) {
            char c2 = text2.at(j - 1); // 当前text2的字符（j-1是实际索引）
            
            if (c1 == c2) {
                // 若当前字符相同，LCS长度 = 两个字符串都去掉当前字符后的LCS长度 + 1
                // 即依赖于dp[i-1][j-1]（左上角的值）
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // 若当前字符不同，LCS长度 = 以下两种情况的最大值：
                // 1. text1去掉当前字符，text2保留（dp[i-1][j]，正上方的值）
                // 2. text1保留，text2去掉当前字符（dp[i][j-1]，正左方的值）
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // dp[m][n]即为两个完整字符串的LCS长度
    return dp[m][n];
}

---

（5）整数拆分

leetcode 343：
【问题】

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

【分析】

这个问题难度就好很多了，我们只需要去思考怎么让乘积最大化就可以，如果数学很好的程序员其实已经可以秒了，只要尽可能多拆出来3即可，详细如下：

• 如果 nmod3=0：全拆成 3。

• 如果 nmod3=1：拆成两个 2 和其余 3（因为 3+1 不如 2+2）。

• 如果 nmod3=2：拆成一个 2 和其余 3。

但是我们既然学的动态规划的话，数学神力先放放，我们当然要利用数学在计算机里发光发热，但是我们还在学习阶段，showshow劲儿~ 宝贝~，如果从计算机的动态规划的角度该怎么做？

我们先来从新认识一下动态规划这个过程

在打家劫舍还是爬楼梯，我们侧重于更新状态，即更新 dp[i](old) → dp[i](new)

但是在做LIS和LCS的时候又侧重不断刷新初始值

Anyway，我们其实都是在刷新初始值状态的，只不过在打家劫舍默认为0，爬楼梯给出了目标直接递推就可以 

那我们的状态转移方程式是什么？

无论是多大的数字，我们优先拆成两个数，并优先计算这两个数相乘的值，作为dp[i]的值

（这一思想是因为，首先我们目前只会这么拆，其次，计算机也喜欢简单的运算，最后也是比较关键一点，这是一个最优子结构下的最小子问题）

然后肯定会出现拆完的时候，对应的位置正好是dp[i]所以dp[i]也要更新！

 max(j * (i - j), j * dp[i - j])

然后不断拆，并且筛选大的，然后剩下一个最大值，搞定！

curMax = max(curMax, max(j * (i - j), j * dp[i - j]));

int integerBreak(int n) {
    vector <int> dp(n + 1);
    for (int i = 2; i <= n; i++) {
        int curMax = 0;
        for (int j = 1; j < i; j++) {
            curMax = max(curMax, max(j * (i - j), j * dp[i - j]));
        }
        dp[i] = curMax;
    }
    return dp[n];
}

---

四、背包问题

解释一下背包这个词 他来自一道很经典的题目，即一个有限空间的背包要装尽可能多且高价值的物品，而处理问题的思路与贪心这样的局部最优的思路不一样，于是叫做背包问题，背包问题的分类其实很广泛，应用也很多所以使得这个名字没有简单的归纳成DP

（1）核心思路

状态转移方程的难度有所提升，基本上背包问题的目的都是尽可能装到最大的价值，难度在于限制条件，限但不仅限于，高价值物品太占空间、高价值物品自带一些debuff（比如装了什么什么就不能装）、低价值物品带一些buff（比如可以给高价值物品升值之类的）、亦或者每个物品不能重复装入、以及抽象背包问题，乍一眼感觉更像是多维dp。

（2）0-1背包（东西只能装一次）

LeetCode 416. 分割等和子集

【问题】

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

eg [1,5,5,11] → [1,5,5] , [11]

【分析】

  这个问题直接用一维dp会很麻烦，用二维dp会浪费很多空间，简单观察和思考后，我们发现我们不需要找出两个数组，然后作比较，事实上就是一分为二的事情，只要一个子数组相加之和能够等于整个数组和的一般就可以了！

比如例子中的  [1,5,5,11] → [1,5,5] , [11] 从理想化的角度来说 其实1,5,5这个子数组无所谓，只要我们找到了11这个数字就好了。但是实战很难打出就是了，但是不妨试试，这样运行时间会很理想

从01背包的角度来看：装的价值正好等于 sum/2 这就是我们想要的效果

但是 状态转移方程的难度还是有的，问题在于最小子问题很好描述，但不太好实现，以及最小子问题的最优子结构是什么样的似乎也有点模糊，模拟找规律也不好找，马萨卡，到此为止了嘛……

倒也不用这么悲观，先捋一下我们在dp什么？要找sum/2本身不是很容易的事情，我们的计算机不擅长一口气找一串数字，所以无论会不会做，先把sum/2先拆成若干两两相加，这些两两相加的结果就是一系列目标值，我们用布尔来表示这些目标是否能达成就行，我们会习惯开一个二维dp

但是！ 如果我们在之前的循环中，发现了某一个目标值dp[i][k]是可以实现的，已经没有必要在下一轮找目标值的时候再来一遍，所以每一个目标值的T/F其实是依赖上一轮运行结果的，所以我们可以直接开一个一维dp直接记录T/F而不用一遍遍的更新

然后我们的子结构算是摸清了，状态转移方程也会好说一点，无非就是在一轮轮的验证中更新TF值，最后一个问题 循环次数的依据是什么？

第一个循环：无疑是数组的值  第二个会是什么？根据上述分析你可能已经知道了，即验证目标值是否可以达到，或者目标值在减去数组的值的情况下是否可以达成（有点抽象）

比如[1，5，6] 当 j==6，num==5时，j>=num 那么判断dp[6]本身是否可以达到或者dp[1]是否可以达到，如果可以达到 1（我们希望可以达到的值）+5（num） == 6（j） 所以也可以作为判断依据

#include <vector>
#include <numeric> // for accumulate
using namespace std;

bool canPartition(vector<int>& nums) {
    int totalSum = accumulate(nums.begin(), nums.end(), 0);

    // 总 sum 为奇数，不可能分割
    if (totalSum % 2 != 0) {
        return false;
    }
    int target = totalSum / 2;
    
    // dp[j] 表示是否存在和为 j 的子集
    vector<bool> dp(target + 1, false);
    dp[0] = true; // 初始化：和为 0 的子集存在（空集）
    

    for (int num : nums) {         // 遍历每个物品
        // 0-1 背包：从大到小遍历容量，避免重复使用
        for (int j = target; j >= num; --j) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    
    return dp[target];
}

---

（3）完全背包（东西可以无限次选择）

leetcode 322. 零钱兑换

【问题】

给定不同面额的硬币 coins 和一个总金额 amount，计算凑成总金额所需的最少硬币数。

如果无法凑成，返回 -1

【分析】

这个问题难度不大，本质上就是爬楼梯问题的延伸，爬楼梯时每一步的跨度不再固定，爬到哪里也不再固定，但是基本道理是一样的，只不过有一些楼层爬不到，比如如果面额（只考虑整数）没有1，则无法拥有总金额为1的情况，以及要求方案的最小值而非总方案数，所以我们没有把这个问题直接地分类到线性dp

目标状态很简单dp[j] 表示达到金额j 的最小方案数，因为coin的面额和种类数目是不定的，所以需要遍历coins来正确更新状态

状态转移方程是，dp[j] = min(dp[j], dp[j - coin] + 1)

#include <vector>
#include <climits> // 用于 INT_MAX
using namespace std;

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {

        vector<int> dp(amount + 1, INT_MAX);
        
        // 初始化：凑成金额0需要0个硬币
        dp[0] = 0;
        
        // 遍历每个硬币
        for (int coin : coins) {
            for (int j = coin; j <= amount; ++j) {
                // 如果dp[j - coin]不是初始的INT_MAX，说明可以通过添加当前硬币凑成金额j
                if (dp[j - coin] != INT_MAX) {
                    // 更新最少硬币数：取"不选当前硬币"和"选当前硬币"的最小值
                    dp[j] = min(dp[j], dp[j - coin] + 1);
                }
            }
        }
        
        // 如果最终dp[amount]仍是INT_MAX，说明无法凑成
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

---

（4）多重背包（物品有固定的选取次数上限）

【问题】

改编的零钱兑换

【分析】

多重背包其实一种【限制】的思想，因为现实里很难出现资源无限供应的情况，兜里面很少会恰好带10个1元硬币，也很少能正正好好凑出来一个10元，而多重背包就是模拟你现实情况下的一种策略选取，比如2元硬币只能用3次（只带了3个2元硬币），3元硬币只能用3次（同理），正好凑10元，方案就只能是2+2+3+3，而不能是2+2+2+2+2

因为加上了限制，现在的时间复杂度要再乘上一个常数C

多重背包的应用性较差，效率低，有更好的平替（二进制拆分成若干01背包），很难保证k是个相对小的数字，一些偏难怪的算法竞赛可能会出没。

代码如下： 

#include <vector>
#include <climits>
#include <iostream>
using namespace std;

int main() {
    vector<int> coins = {2, 3};    // 硬币面值
    vector<int> counts = {2, 1};   // 数量限制：2元最多2个，3元最多1个
    int amount = 10;
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;

    for (int i = 0; i < coins.size(); ++i) {
        int coin = coins[i];
        int count = counts[i];
        // 多重背包：逆序遍历金额，避免超过数量限制
        for (int j = amount; j >= coin; --j) {
            // 枚举使用次数 t（1到count，且 t*coin <= j）
            for (int t = 1; t <= count && t * coin <= j; ++t) {
                if (dp[j - t * coin] != INT_MAX) {
                    dp[j] = min(dp[j], dp[j - t * coin] + t);
                }
            }
        }
    }

    int result = (dp[10] == INT_MAX) ? -1 : dp[10];
    cout << "多重背包（有数量限制）：最少 " << result << " 个硬币" << endl;
    // 答案：-1（因为 2元最多2个（共4元），3元最多1个（3元），总计4+3=7 <10，无法凑出）
    return 0;
}

---

（5）分组背包（物品被分为多个组，每组中最多选择一个物品）

leetcode 1155. 掷骰子的 N 种方法

【问题】

有 d 个骰子，每个骰子有 f 个面（点数为 1-f），求掷出的总点数为 target 的不同方法数。

【分析】

总共有d组，筛子面分别相加，凑target，虽然硬说d个for循环也能做，但是想拿一份offer 的话还是乖乖听话学背包吧

有个隐形的约束条件，就是每个组都得选，也就是说如果 target<d 直接return 0即可

经历过线性dp，01背包、完全背包的你，应该不会对着到题感到太困惑，无非是更新dp[i][j]，其中i 表示前 i 个组数，dp [i][j] 表示对应的是前 i 个筛子投出点数 j 的方案数

状态转移方程很简单，就是前 i 个 骰子投出点数 j 的方案数为 当前的方案数 加上 前 i-1 个 骰子投出点数j-k（k为当前骰子投出来的点数）

dp[i][j] += dp[i-1][j - k];

#include <vector>
using namespace std;

class Solution {
public:
    int numRollsToTarget(int d, int f, int target) {
        vector<vector<int>> dp(d + 1, vector<int>(target + 1, 0));
        dp[0][0] = 1; // 初始化：0个骰子掷出0点有1种方法
        
        for (int i = 1; i <= d; ++i) { // 遍历每组（每个骰子）
            for (int j = i; j <= target; ++j) { // 点数至少为i（每个骰子至少1点）
                // 枚举当前骰子的点数k（组内物品）
                for (int k = 1; k <= f && k <= j; ++k) {
                    dp[i][j] += dp[i-1][j - k];
                }
            }
        }
        return dp[d][target];
    }
};

---

五、区间dp

（1）核心思路

这类题目的特点是要保持或者找到一个状态，比如回文子序列，要找到一个序列具有回文的状态，或者递增数组，保持递增的状态，不断的检查子区间是否符合要求的dp过程。难点在于状态转移方程在不同题境下不同，子问题清晰，但是能不能找到怎么做，是另一码事情。

（2）最长回文子序列

leetcode.5

【问题】

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

【分析】

如果之前系统性学过暴力算法，你可能会用中心扩展法，诚然这种方法很巧，空间复杂度为常数，且从性能上来讲确实比动态规划要优秀很多，但是我们的学习目的不在此，这也是一道比较经典的区间dp的题目。

首先对于一个回文序列“abcdcba”，如果从动态规划的角度怎么理解呢？也就是如何把这个问题转化成一个可以“一层一层拨开的洋葱”，如果我们先把前后的‘a’去掉，剩下的子串仍符合序列，直到只剩下一个字母或者为空，即可判定该子串为回文串

其次，如何判断这个序列最长呢？ 不断更新呗~还想咋？

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j]会用布尔值（1/0）来表示是否为回文子串，i为左边界，j为右边界。
        vector<vector<int>> dp(n, vector<int>(n));

        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= n; L++) {
            // 枚举左边界
            for (int i = 0; i < n; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= n) {
                    break;
                }

                if (s[i] != s[j]) {
                    dp[i][j] = false;
                } else {
                    //如果左右边界距离为3或2,那么肯定为回文 eg. aba，aa
                    if (j - i < 3) {
                        dp[i][j] = true;
                   }else{//如果边界距离更大，该串是不是回文串，则取决于串的边界内部是否是回文串
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        //不解释
        return s.substr(begin, maxLen);
    }
};

（3）矩阵链乘法

已知3个矩阵A、B、C尺寸为 （10*30）（30*5）（5*60）

如果 (A*B)*C 计算次数为 4500

如果 A*(B*C) 计算次数为 27000

所以我们需要找到一个最优方案，来提升效率，其他思想和上题相似

pair<int, vector<vector<int>>> matrixChainOrder(const vector<int>& p) {
    int n = p.size() - 1; // 矩阵数量 = 维度数组长度 - 1
    // dp[i][j]：计算矩阵链A[i..j]的最小代价
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    // split[i][j]：记录A[i..j]的最优分割点k
    vector<vector<int>> split(n + 1, vector<int>(n + 1, 0));

    // 初始化：单个矩阵的代价为0（已默认初始化）

    // 按区间长度递增计算（len=1时已初始化，从len=2开始）
    for (int len = 2; len <= n; ++len) {
        // 枚举左端点i（1-based索引）
        for (int i = 1; i + len - 1 <= n; ++i) {
            int j = i + len - 1; // 右端点j
            dp[i][j] = INT_MAX;  // 初始化为无穷大

            // 枚举分割点k（i ≤ k < j）
            for (int k = i; k < j; ++k) {
                // 计算当前分割的总代价：左半部分代价 + 右半部分代价 + 合并代价
                int cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
                // 更新最小代价和分割点
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                    split[i][j] = k; // 记录最优分割点
                }
            }
        }
    }

    return {dp[1][n], split};
}

六、压缩状态dp

(这个有点算是dp里最难的一个part，纯抽象、纯难想、纯不好理解了属于是，我自己都有点拿不准)

（1）核心思想

所谓的状态压缩就是要求我们要用简单的二进制数来表示状态，把复杂的状态空间压缩到可控范围，用于解决一些状态不好表示的问题，比如网格覆盖问题，很难直接在某一个具体的格子，或者变量上做修改

（2）旅行商问题 TSP

leetcode943 超级最短串（最幼稚的名字给心灵打了最高的暴击呢……）

【问题】

给定一个字符串数组 words，找到以 words 中每个字符串作为子字符串的最短字符串。如果有多个有效最短字符串满足题目条件，返回其中 任意一个 即可。

题目有点难懂，简单给大家翻译一下，比如  words[yes，say，sleep] 在正常情况下我们举出来一个字符串（超级串）使得所有word都可以在这个字符串中找到，最简单的超级串是“yessaysleep”，但是我们发现有些部分可以重叠简化，于是我们得到了超级最短串“sayesleep”

我们可以假设 words 中没有字符串是 words 中另一个字符串的子字符串。（虽然给了假设但我们仍可以做一个判断来简化状态）

【分析】

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 计算 s 的后缀与 t 的前缀的最大重叠长度
int maxOverlap(const string& s, const string& t) {
    int maxLen = 0;
    int sLen = s.size(), tLen = t.size();
    // 从最大可能重叠长度开始检查（优化效率）
    for (int len = min(sLen, tLen); len > 0; --len) {
        if (s.substr(sLen - len) == t.substr(0, len)) {
            maxLen = len;
            break; // 找到最大的，直接返回
        }
    }
    return maxLen;
}

// 筛选：去掉被其他字符串包含的字符串（优化：减少n的大小）
vector<string> filterStrings(vector<string>& strs) {
    vector<string> res;
    int n = strs.size();
    for (int i = 0; i < n; ++i) {
        bool isSub = false;
        for (int j = 0; j < n; ++j) {
            if (i != j && strs[j].find(strs[i]) != string::npos) {
                isSub = true;
                break;
            }
        }
        if (!isSub) res.push_back(strs[i]);
    }
    return res;
}

string shortestSuperstring(vector<string>& strs) {
    // 步骤1：筛选必要字符串（去掉被包含的）
    vector<string> filtered = filterStrings(strs);
    int n = filtered.size();
    if (n == 0) return "";
    if (n == 1) return filtered[0];

    // 步骤2：预处理重叠矩阵
    vector<vector<int>> overlap(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != j) {
                overlap[i][j] = maxOverlap(filtered[i], filtered[j]);
            }
        }
    }

    // 步骤3：初始化 DP 表
    vector<vector<string>> dp(1 << n, vector<string>(n, ""));
    for (int i = 0; i < n; ++i) {
        dp[1 << i][i] = filtered[i];
    }

    // 步骤4：状态转移
    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int i = 0; i < n; ++i) {
            // 只有 mask 包含 i 时，才可能作为结尾
            if (!(mask & (1 << i))) continue;
            // 尝试添加未使用的字符串 j
            for (int j = 0; j < n; ++j) {
                if (mask & (1 << j)) continue; // j 已使用，跳过
                int newMask = mask | (1 << j);
                // 拼接 i 和 j（跳过重叠部分）
                string newStr = dp[mask][i] + filtered[j].substr(overlap[i][j]);
                // 更新 dp[newMask][j] 为更短的字符串
                if (dp[newMask][j].empty() || newStr.size() < dp[newMask][j].size()) {
                    dp[newMask][j] = newStr;
                }
            }
        }
    }

    // 步骤5：提取结果（全使用状态下的最短字符串）
    int fullMask = (1 << n) - 1;
    string ans = dp[fullMask][0];
    for (int i = 1; i < n; ++i) {
        if (dp[fullMask][i].size() < ans.size()) {
            ans = dp[fullMask][i];
        }
    }
    return ans;
}

（3）最短 Hamiltonian 路径（也叫蒙德里安的梦想）

acwing 291

【问题】

求用 1×2 和 2×1 的骨牌铺满 M×N 网格的方案数。

【分析】

本质上是一个可以旋转的长砖，只要不多不少的铺满就好了，但是好死不死非要得到所有的方案数

状态dp[i][j]，对于这一类问题，我们要在意的点是什么？就是我当前铺的有没有铺过，以及哪里还没铺，显然对于dp[0][0]是都没铺的，所以我们将 i 认定为前面的i-1行都铺好了， j 则表示第i行是否有多余的砖头

转移，毕竟是要方案数，所以直接让dp[i][j] += dp[i-1][k]，dp[0][0]=1

return dp[N][0]，前N铺满且当前行没有多余的砖头

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 12;
const int MAXM = 1 << MAXN;

long long dp[MAXN + 1][MAXM];  // dp[i][j]：前 i-1 行铺满，第 i 行状态 j
vector<int> valid;  // 合法的状态（连续 0 段长度为偶数）
int n, m;

// 检查状态 s 是否合法（连续 0 段长度为偶数）
bool is_valid(int s) {
    int cnt = 0;  // 当前连续 0 的个数
    for (int i = 0; i < m; ++i) {
        if (s & (1 << i)) {
            if (cnt % 2 != 0) return false;
            cnt = 0;
        } else {
            cnt++;
        }
    }
    return cnt % 2 == 0;
}

int main() {
    while (cin >> n >> m, n || m) {
        // 预处理合法状态
        valid.clear();
        for (int s = 0; s < (1 << m); ++s) {
            if (is_valid(s)) valid.push_back(s);
        }

        // 初始化 DP
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;

        // 状态转移
        for (int i = 1; i <= n; ++i) {
            for (int j : valid) {  // 第 i 行状态 j
                for (int k : valid) {  // 第 i-1 行状态 k
                    if ((j & k) == 0) {  // 状态兼容
                        dp[i][j] += dp[i-1][k];
                    }
                }
            }
        }

        cout << dp[n][0] << endl;
    }
    return 0;
}

七、树形 DP（待填坑）

（1）核心思路

（2）树的直径

（3）二叉树中的最大路径和

（4）打家劫舍 |||