DP状态定义必须精确，如LIS中dp[i]应明确为“以nums[i]结尾的严格递增子序列最大长度”；转移前须确保j合法且nums[j]
DP状态定义不明确，程序就跑不起来
动态规划在C++里不是靠套模板，而是靠想清楚「状态是什么」。比如求最长上升子序列，dp[i] 不能模糊地写成“以第i个数结尾的答案”，得明确是「以nums[i]结尾的严格递增子序列的最大长度」——少一个限定词，转移时就可能越界或漏情况。
常见错误现象：dp[i] = max(dp[j] + 1) 中没加 nums[j] 判断，结果全算成最长子数组；或者把状态设成「前i个数中的LIS长度」，导致无法转移（因为不知道末尾值，没法接新数）。
- 状态必须可转移：能从已有状态推出新状态，且只依赖更小的索引或已计算子问题
- 状态维度要够用：一维不够就加维，比如背包问题加容量维度 →
dp[i][w] - 初始化别硬填0：
dp[0] = 1是常识，但像区间DP常要初始化所有dp[i][i] = 1或0，取决于问题语义
vector初始化大小和默认值容易出错
C++里vector不初始化就访问会UB，而DP几乎全靠它存状态。比如想开二维dp[n][m]，写成 vector<vector>> dp(n, vector<int>(m))</int></vector> 没问题，但若漏掉第二层大小：vector<vector>> dp(n)</vector>，后续dp[i].push_back(...) 就变成模拟而非随机访问，时间复杂度直接升到O(n²)甚至更高。
使用场景：刷题常用vector，但工程中若确定尺寸且性能敏感，array或裸数组更快；不过DP题基本都用vector，因为n常由输入决定。
立即学习“C++免费学习笔记（深入）”；
- 初始化带默认值更安全：
vector<int> dp(n, -1)</int>比vector<int>(n)</int>更易调试（-1比0更容易暴露未更新状态） - 滚动数组优化时，别只改
dp变量名不改尺寸：比如从dp[i][j]压到dp[j]，仍需保证dp大小 ≥ m，否则越界 - 注意
vector构造函数参数顺序：vector<int>(size, value)</int>，反了会创建一堆0再赋值，白耗内存
状态转移时忘记边界检查和条件过滤
写for (int j = 0; j 然后直接<code>if (dp[j] > 0) dp[i] = max(dp[i], dp[j] + 1)，看着没问题，但实际可能因j对应的状态根本不可达（比如背包里重量超限），导致用无效值更新答案。
典型错误：在01背包中，内层循环从w = weight[i]开始是对的，但有人写成for (int w = 0; w ，然后<code>if (w >= weight[i])，逻辑对但效率低；更糟的是漏掉if，直接访问dp[w - weight[i]]，造成负索引越界。
- 所有下标访问前必须检查是否在合法范围内：
j >= 0 && j ，尤其滚动数组里<code>w - weight[i]可能为负 - 条件判断要和状态定义严格对齐：比如「恰好装满」背包要求初始化
dp[0] = 0、其余为-INF，否则dp[W]可能来自未装满的中间状态 - 浮点DP慎用
==比较：用abs(a - b) ，否则<code>dp[i] == dp[j]可能永远为假
记忆化搜索 vs 递推：选错实现方式会卡死或超内存
纯递归+memo适合状态稀疏或转移方向不规则的问题（比如某些博弈DP、树形DP），而填表式递推更适合状态密集、有明确方向的问题（如LIS、背包）。用记忆化硬写背包，最坏可能递归深度达W，爆栈；用递推硬写某些图上DP，可能遍历大量无效状态，TLE。
性能影响明显：记忆化平均只算真正需要的状态，但每次函数调用有开销；递推无调用开销，但可能填满整个dp表，空间多一倍（比如二维压成一维后还多开一行）。
- 先画状态依赖图：如果依赖关系是DAG且边稀疏，优先记忆化；如果能按索引单调推进（i→i+1，w→w+1），递推更稳
-
memo数组别用map存二维键：map<pair>, int></pair>比vector<vector>></vector>慢10倍以上，除非状态确实非常稀疏 - 递推注意循环顺序：01背包倒序，完全背包正序，写反了就变成无限物品——这不是bug，是逻辑错，调试时很难一眼看出
状态设计不对，后面全是白忙；边界不守，程序当场崩；选错实现方式，可能本地快但评测机上栈溢出或MLE。这些地方没有银弹，只能一个个case抠。
