区间动态规划
介绍
区间 DP 是状态的定义和转移都与区间有关，其中区间用两个端点表示。
区间动态规划 一般是定义dp[i][j]，表示考虑[i..j]范围内的元素，原问题的解增加i，减小j都可以得到更小规模的子问题。推导状态一般是按照区间长度从短到长推的
区间动态规划状态转移 推导状态dp[i][j]时，有两种常见情况:
- dp[i][j]仅与常 数个更小规模问题有关,方程为:
dp[i][j]=f(dp[i+1][j],dp[i][j-1],dp[i+1][j-1])
:::details 点击查看图片 :::
- dp[i][j]与O(n)个更小规模子问题有关,一般是枚举[i,j]的分割点，将区间分为[i,k]和[k+1,j],对每个k分别求解。方程为:
dp[i][j]=g(f(dp[i][k],dp[k+1][j])), 其中k=i……j-1.
:::details 点击查看图片 :::