请举一个动态规划经典问题，并说明如何对其做空间复杂度优化。

Question

Accepted Answer

考察点：考察动态规划建模能力与空间优化意识。回答思路：准确描述一个经典DP问题及其状态转移 说明原始空间复杂度并指出冗余状态 给出具体空间优化方案并分析正确性 讨论降维对遍历顺序等边界条件的影响

考察说明