多维数组适合动态规划因其能天然映射多维状态空间；如0-1背包用dpi、lcs用dpi分别刻画物品数与容量、两字符串前缀的最优解，且可通过降维或按内存布局优化提升效率。
多维数组是动态规划最常用的存储载体，它天然适配多维状态空间——当一个问题需要同时跟踪多个变化维度（比如物品数量、背包容量、字符串位置、时间步长），二维或更高维数组就能清晰刻画每个状态的最优解。
为什么多维数组适合动态规划
动态规划依赖“状态”来记录子问题的解。一维数组只能表达单一变量的变化，而现实中的优化问题往往受多个因素制约。例如：
- 0-1背包问题：需同时考虑“前i个物品”和“当前容量j”，用dp[i][j]表示最自然；
- 最长公共子序列（LCS）：需对齐两个字符串的下标，dp[i][j]表示X前i个字符与Y前j个字符的LCS长度；
- 编辑距离：涉及源串位置、目标串位置、操作类型，常需二维甚至三维数组建模。
典型二维结构的设计逻辑
以LCS为例，核心在于理解数组下标与实际含义的映射：
- dp[i][j] 不代表“第i行第j列”，而是“X[0..i−1] 和 Y[0..j−1] 的最长公共子序列长度”；
- 初始化时让dp[0][*] = dp[*][0] = 0，对应空字符串的边界；
- 状态转移只依赖左、上、左上三个邻居，体现“无后效性”——过去决策不影响后续转移方向。
空间优化的常见做法
并非所有场景都必须保留完整多维表。当状态转移仅依赖前一行或前一列时，可降维节省内存：
- 斐波那契类线性递推：从O(n)空间压缩到O(1)，只存前两个值；
- LCS若只需长度不需构造路径：二维dp[i][j]可简化为两个一维数组prev[]和curr[]；
- 背包问题中，若物品可重复使用（完全背包），内层循环正向遍历即可复用同一数组；若不可重复（0-1背包），则需倒序避免覆盖未使用的旧值。
三维及以上数组的应用提示
当约束条件增加，比如“带冷却期的股票买卖”或“双约束背包（重量+体积）”，就需要第三维：
- 定义dp[i][j][k]时，明确每一维物理意义（如i=天数，j=是否持有，k=已交易次数）；
- 初始化更关键——无效状态常设为负无穷或极小值，确保不干扰合法转移；
- 访问时注意内存局部性：C/C++按行优先存储，嵌套循环中**最右下标应放在内层循环**，提升缓存命中率。
