【GESP】C++七级考试大纲知识点梳理, (2) 复杂动态规划

GESP C++七级考试大纲的第2条考点是整个七级的“重头戏”——复杂动态规划。相比于低级别的线性DP，七级要求掌握更复杂的模型（如区间DP）以及处理两个序列的问题（LCS），同时对空间复杂度优化提出了明确要求。

（2）掌握复杂动态规划（二维动态规划、动态规划最值优化）。包括区间动态规划、最长上升子序列（LIS）、最长公共子序列（LCS）等内容，理解基于滚动数组等降低动态规划空间复杂度的方法。

动态规划（DP）的核心在于状态定义和状态转移方程。七级考试中，题目往往不会直接告诉你“我是DP题”，需要你通过观察“最优子结构”和“重叠子问题”来发现。

本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。

全文详见：https://www.coderli.com/gesp-7-exam-syllabus-complex-dp/

https://www.coderli.com/gesp-7-exam-syllabus-complex-dp/https://www.coderli.com/gesp-7-exam-syllabus-complex-dp/