4.13博客

区间dp

区间DP最简单形式的伪代码(具体要根据题目修改)

for(int i=1;i<=n;i++)
{
    dp[i][i]=初始值
}
for(int len=2;len<=n;len++)  //区间长度
for(int i=1;i<=n;i++)        //枚举起点
{
    int j=i+len-1;           //区间终点
    if(j>n) break;           //越界结束
    for(int k=i;k<j;k++)     //枚举分割点，构造状态转移方程
    {
        dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);
    }
}

一定要再写一遍这个源代码，这个源代码一定要记住，在做题时这个用到太多了。

最近继续做题吧。我发现看资料其实并不能理解太多，只有做题才能更加深入的理解。