区间DP

区间DP是一类很常见的DP类型

其解法通常固定,依次枚举区间长度、左端点、断点

例题

石子合并

设$dp[i][j]$为将$i\rightarrow j$合并的最大(小)代价,$sum[i]$为$a[1]+…+a[i]$的值

从小到大枚举$len,l,k$,可得转移方程

$$dp[i][i+len-1]=max(dp[i][i+len-1],dp[i][k]+dp[k+1][i+len-1]+sum[i+len-1]-sum[i-1]$$

$$dp[i][i+len-1]=min(dp[i][i+len-1],dp[i][k]+dp[k+1][i+len-1]+sum[i+len-1]-sum[i-1]$$

由于题目要求最大值和最小值,所以需计算两次

另外该题是一个环,所以要将整个数列$1…n$复制到$n+1…2n$,然后在枚举的时候注意一下范围,时间复杂度$O(n^3)$

能量项链

我们观察一组数据$(2,3),(3,5),(5,10)$的合并代价分别是:$235+2510$和$3510+2310$

所以对于$a[i],a[i+1],a[i+2],a[i+3]$的合并代价有两种

  • $a[i]*a[i+1]*a[i+2]+a[i]*a[i+2]*a[i+3]$
  • $a[i+1]*a[i+2]*a[i+3]+a[i]*a[i+1]*a[i+3]$

在实际转移中$k$其实就等于$i+1$,$j$等于$i+3$

所以在状态转移的过程中只需要考虑这两种合并方式的大小,因为无论如何合并最后的状态都是不变的

设$dp[i][j]$为将$i\rightarrow j$合并的最大代价

转移方程可以得到

$$dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+max(a[i]*a[k]*a[k+1]+a[i]*a[k+1]*a[j],a[k]*a[k+1]*a[j]+a[i]*a[k]*a[j]))$$

最后的环的处理和石子合并相似,时间复杂度$O(n^3)$