L1547题涉及到基本概念-区间dp问题

来源：13-6 更复杂度的动态规划状态（1）

qyholy

2021-03-19

起初看老师定义的dp意思，思考了很久没看懂，没看到的点是第一层循环，即枚举i~j之间的区间距离，不太懂这么做的本质是什么，老师可以讲解下区间DP吗？

写回答

1回答

javaman

2021-03-20

您好，不用太纠结于名称。

其实就是dp的状态表示是一个区间，或者说是一条线段。所以用[i][j]表示两个端点。

通常是 dp[i][j] = min/max(dp[i][k], dp[k + 1][j]) 类似于如此。

所以整个区间的最优解，变为枚举分点k。

因为[i, k]和[k + 1, j]都比[i, j]短，所以我们通常可以由长度从小到大递推，这样报称我们用已经计算过的值来推出要计算的值。

算法面试刷题课--竞赛命题人带你刷70+高质量题型

只需20小时， Google面试官带你完成Java算法面试准备

539 学习 · 65 问题

相似问题

回答 1

回答 2

回答 1

回答 1

回答 1