以下为摘要

区间dp能解决的问题就是通过小区间更新大区间，最后得出指定区间的最优解

个人认为，想要用区间dp解决问题，首先要确定一个大问题能够剖分成几个相同较小问题，且小问题很容易组合成大问题，从而从解决小问题逐渐解决大问题，体现的其实是分治的思想，只不过是通过dp用递推的方式解决了。比如floyd现在看来也属于区间dp 的一种。

然后是自己的理解及几个例子

区间DP，思路在于由小区间刷新大区间，具体做法是：

最外层循环枚举区间长度（从小到大，先计算小区间来刷新大区间）
第二层枚举大区间起点i
依据起点和长度计算终点j
第三层循环在i与j中枚举k，即为把大区间分为两个小区间的断点
依题意计算，取较大值刷新大区间

以下是几个例子：

P1063 能量项链

    for(int len = 2;len <= num + 1;len++){

            for(int i = 1;i + len - 1 <= 2 * num/*j不能超过总数*/;i++){

                int j = i + len - 1;

                //dp[i][j] = 0;

                for(int k = i + 1;k < j;k++){

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

                    }

                }

            }

P1880 石子合并

    for(int len = 2;len <= num;len++){

            for(int i = 1;i <= num * 2 - (len - 1);i++){

                int j = i + len - 1;

                d1[i][j] = 0;

                d2[i][j] = 99999999;

                for(int k = i;k < j;k++){

                    //cout<<d2[i][k] + d2[k + 1][j] + mmp[i][j]<<endl;

                    d1[i][j] = max(d1[i][j],d1[i][k] + d1[k + 1][j] + mmp[i][j]);

                    d2[i][j] = min(d2[i][j],d2[i][k] + d2[k + 1][j] + mmp[i][j]);

                    }

                }

            }

P2904 [USACO08MAR]跨河（这个有区间DP思想，但方法步骤不同）

    dp[0] = 0;

        for(int i = 1;i <= num;i++){

            for(int j = 1;j <= i;j++){

                //cout<<"i= "<<i<<endl;

                //cout<<dp[i]<<" "<<dp[i - j] + tim[j]<<endl;

                dp[i] = min(dp[i],dp[i - j] + tim[j]);//分为j和i-j两部分，螺旋枚举，找最小；

                }

            }

具体代码参见测评记录

巴特西

区间DP的思路（摘自NewErA）及自己的心得

以下为摘要

然后是自己的理解及几个例子

最新文章

热门文章