【C++题解】DP入门-LISLCS

4小时动态规划（DP）入门练习计划。我们将聚焦于两个最经典的线性DP模型：最长递增子序列（LIS）和最长公共子序列（LCS），帮助您初步建立DP的系统性思考模式。

下午 (4小时): 动态规划入门——LIS & LCS

动态规划（Dynamic Programming）是算法竞赛中的核心内容，其思想在于将复杂问题分解为更小的、可重用的子问题，并通过记录子问题的解来避免重复计算。今天我们将从最基础的线性DP入手。

练习计划概览

• 总时长: 约 4 小时

• 核心目标:

  1. 理解动态规划的两个核心要素：最优子结构和重叠子问题。

  2. 掌握定义DP状态 dp[i] 的方法，即思考 dp[i] 应该表示什么物理意义。

  3. 学习推导状态转移方程，这是DP的灵魂，即如何从已知的子问题解推导出当前问题的解。

  4. 从一维DP（LIS）过渡到二维DP（LCS），建立处理双序列问题的DP思维模型。

第一部分：最长递增子序列 (LIS) —— 一维DP的基石 (约 1.5 小时)

LIS问题是线性DP中最经典的问题之一。通过它，您可以学习到一维DP问题最核心的分析方法：思考以第 i 个元素结尾的子问题。

题解

//300 - 理解动规五步法，后面我先不写了。#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;class Solution {
public:int lengthOfLIS(vector<int>& nums) {if (nums.empty()) return 0;vector<int> dp(nums.size(), 1);int maxLen = 1;for(int i = 1; i < nums.size(); i++){for(int j = 0; j < i; j++){if(nums[i] > nums[j] && dp[i] <= dp[j]){dp[i] = dp[j] + 1;}}if(dp[i] > maxLen)maxLen = dp[i];}return maxLen;}
};int main() {Solution solution;// 测试用例1: [10,9,2,5,3,7,101,18]vector<int> nums1 = {10, 9, 2, 5, 3, 7, 101, 18};cout << "测试用例1: [10,9,2,5,3,7,101,18]" << endl;cout << "最长递增子序列长度: " << solution.lengthOfLIS(nums1) << endl;cout << "期望结果: 4 (子序列: [2,3,7,18])" << endl << endl;// 测试用例2: [0,1,0,3,2,3]vector<int> nums2 = {0, 1, 0, 3, 2, 3};cout << "测试用例2: [0,1,0,3,2,3]" << endl;cout << "最长递增子序列长度: " << solution.lengthOfLIS(nums2) << endl;cout << "期望结果: 4 (子序列: [0,1,2,3])" << endl << endl;// 测试用例3: [7,7,7,7,7,7,7]vector<int> nums3 = {7, 7, 7, 7, 7, 7, 7};cout << "测试用例3: [7,7,7,7,7,7,7]" << endl;cout << "最长递增子序列长度: " << solution.lengthOfLIS(nums3) << endl;cout << "期望结果: 1 (所有元素相同)" << endl << endl;// 测试用例4: [1,3,6,7,9,4,10,5,6]vector<int> nums4 = {1, 3, 6, 7, 9, 4, 10, 5, 6};cout << "测试用例4: [1,3,6,7,9,4,10,5,6]" << endl;cout << "最长递增子序列长度: " << solution.lengthOfLIS(nums4) << endl;cout << "期望结果: 6 (子序列: [1,3,4,5,6,10] 或 [1,3,6,7,9,10])" << endl << endl;// 测试用例5: 空数组vector<int> nums5 = {};cout << "测试用例5: []" << endl;cout << "最长递增子序列长度: " << solution.lengthOfLIS(nums5) << endl;cout << "期望结果: 0 (空数组)" << endl << endl;return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;int main(){int n;cin >> n;vector<int> v(n);for(int i=0;i<n;i++){cin >> v[i];}vector<int> dp1(n,1);vector<int> dp2(n,1);for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(v[i]>v[j]){dp1[i] = max(dp1[i],dp1[j]+1);}}}int maxnums=0;for(int i=n-2;i>=0;i--){for(int j=n-1;j>i;j--){if(v[i]>v[j]){dp2[i] = max(dp2[i],dp2[j]+1);}}if(dp1[i]+dp2[i]>maxnums){maxnums = dp1[i]+dp2[i]-1;}}   if(dp1[n-1]+dp2[n-1]>maxnums){maxnums = dp1[n-1]+dp2[n-1]-1;}cout << n-maxnums;return 0;
}

练习建议:

• 动手推导: 在做 LIS 时，不要直接看题解。找一个短数组（如 [10, 9, 2, 5, 3, 7, 101, 18]），亲手在纸上填 dp 数组的每一项，深刻理解 dp[i] = max(dp[j] + 1) 这个转移方程的含义。

• 理解状态定义: 务必理解 dp[i] 的精确定义——它是“以 nums[i] 结尾”的，而不是“前 i 个数”的。这是线性DP中一个常见且关键的区别。

• 进阶思考 (选做): LIS 存在一个 O(n log n) 的优化解法（贪心+二分）。在完全掌握 O(n²) 的DP解法后，如果时间充裕，可以尝试理解这个更优的解法。

第二部分：最长公共子序列 (LCS) —— 二维DP的典型 (约 2 小时)

当问题涉及两个序列或字符串时，我们通常需要一个二维的 dp 数组来描述状态。LCS 是这类问题的绝佳入门范例。

题解

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>using namespace std;class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));for (int i = 1; i <= text1.size(); i++) {for (int j = 1; j <= text2.size(); j++) {if (text1[i - 1] == text2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[text1.size()][text2.size()];}
};// 测试函数
int main() {Solution solution;// 测试用例1string text1 = "abcde";string text2 = "ace";cout << "测试用例1: text1=\"" << text1 << "\", text2=\"" << text2 << "\"" << endl;cout << "最长公共子序列长度: " << solution.longestCommonSubsequence(text1, text2) << endl;cout << "期望结果: 3" << endl << endl;// 测试用例2text1 = "abc";text2 = "abc";cout << "测试用例2: text1=\"" << text1 << "\", text2=\"" << text2 << "\"" << endl;cout << "最长公共子序列长度: " << solution.longestCommonSubsequence(text1, text2) << endl;cout << "期望结果: 3" << endl << endl;// 测试用例3text1 = "abc";text2 = "def";cout << "测试用例3: text1=\"" << text1 << "\", text2=\"" << text2 << "\"" << endl;cout << "最长公共子序列长度: " << solution.longestCommonSubsequence(text1, text2) << endl;cout << "期望结果: 0" << endl << endl;return 0;
}

练习建议:

• 画出DP表格: 对于LCS和编辑距离，解决问题的最好方法就是在纸上画一个二维表格，手动填写 dp[i][j] 的值。这能帮助您清晰地看到状态是如何从左上方向右下方逐步转移和构建的。

• 注意下标: 在使用二维DP处理字符串问题时，要特别注意字符串下标（通常从0开始）和 dp 数组下标（通常从1开始，dp[0][...] 和 dp[...][0] 作为边界）的对应关系，避免差一错误。

目标达成自查 (约 0.5 小时)

完成以上练习后，进行复盘和总结：

1. DP三部曲是什么？

   • 定义状态：dp[i] 或 dp[i][j] 代表的物理意义是什么？

   • 状态转移方程：如何从已知的子问题解推导出当前状态？

   • 初始化/边界条件：dp[0] 或 dp[0][0] 应该是什么？

2. LIS vs LCS：

   • 为什么LIS是一维DP，而LCS是二维DP？（LIS处理单个序列，状态只与位置 i 有关；LCS处理两个序列，状态与两个序列的位置 i 和 j 都有关）。

3. 子序列 vs 子串：

   • 子序列（Subsequence）和子串（Substring）有什么区别？（子序列可以不连续，子串必须连续）。

   • 这个区别如何体现在DP的状态转移方程中？（LCS中 dp[i-1][j] 和 dp[i][j-1] 的转移体现了“可以不连续”的特性）。

4. 空间优化:

   • 思考一下，在计算 dp[i][j] 时，我们实际上只用到了上一行和当前行的数据。基于此，能否将二维 dp 数组优化成一维的（滚动数组）？（这是DP中常见的空间优化技巧）。