最基本的思想依旧是分治，对于每段区间都由更小的区间最优值组合得到。

Step://模板 //区间最优解

变量：

         dp[i][j]：区间[i,j]的最优解（dp[i][i]对角线视情况而定）；

         k：每次将区间[i,j]分为更小的区间组合[i,k]+[k,j]；

三层循环：

         最外层：for(int l=1;l<=len;l++) //区间长度枚举

         第二层：for(int i=1;i<=len-l+1;i++)  //起点+终点枚举

                     int j=i+l-1; dp[i][j]=***;

          内层： for(int k=i;k<j;k++)  //枚举区间内部分割点k

                      dp[i][j]=max/min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sun[i-1]);

Step://模板 //区间计数 //另一种写法？？  //还是要灵活一点，这些是最最简单基础的板子

变量：

         dp[i][j]：区间[i,j]的最优解（dp[i][i]对角线视情况而定）；

         k：每次将区间[i,j]分为更小的区间组合[i,k]+[k,j]；

         记得初始化dp；

三层循环：

         最外层：for(int i=1;i<=n;i++)  //枚举起点

         第二层：for(int j=i+1;j<=n;j++ //终点枚举

                     //有时需要处理dp[i][j]

          内层： for(int k=i;k<=j;k++)  //枚举区间内部分割点k

                      dp[][]递推式

简单的基础题（中文题……不解释）：

1.石子归并

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int n, sum[105],a;int dp[105][105];int main(){    while (cin>>n)    {        sum[0] = 0;        for (int i = 1; i <= n; i++)        {            scanf("%d", &a);            sum[i] = sum[i - 1] + a;        }        memset(dp, 0, sizeof(dp));        for(int l=2;l<=n;l++)            for (int i = 1; i <= n - 1 + 1; i++)            {                int j = i + l - 1;                dp[i][j] = 0x3f3f3f3f;                for (int k = i; k < j; k++)                {                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i - 1]);                }            }        printf("%d\n", dp[1][n]);    }    return 0;}
        
       
      
     

POJ 2955 括号匹配

求括号匹配的最大值

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;int n;int dp[110][110];string s;int main(){    while (cin>>s)    {        int len = s.length();        memset(dp, 0, sizeof(dp));        for(int l=2;l<=len;l++)            for (int i = 0; i <= len - l+1 ; i++)            {                int j = i + l-1 ;                if ((s[i] =='('&& s[j]==')')||(s[i]=='['&&s[j]==']'))                    dp[i][j] = dp[i + 1][j - 1] + 2;                else dp[i][j] = dp[i + 1][j - 1];                for (int k = i; k < j; k++)                {                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);                }            }        cout << dp[0][len - 1] << endl;    }    return 0;}
         
        
       
      
     

改了好久啊……这个……

emmmmmmm跟前面的题还是稍微有些不太一样，这里需要逆向推(正向推的话，需要考虑的情况有很多，当前衣服跟前面的衣服有没有一样的啊，是脱了还是还在里面套着啥的……总之就是很乱很杂的感觉？？但是，如果逆向考虑的话，只需要看当前衣服是不是只在此时使用)，下面来看一看递推的式子↓

很容易想到，如果最i处的衣服只在i处使用，那么dp[i][j]=dp[i+1][j]+1；

                    如果i处衣服在j处也使用的话（a[i]==a[j]）,那么dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j]);

ps：不要忘记初始化dp

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;int n,a[110],t;int dp[110][110];int main(){    cin >> t;    int cnt = 0;    while (t--)    {        cin >> n;        memset(dp, 0, sizeof(dp));        for (int i = 1; i <= n; i++)        {            cin >> a[i];            dp[i][i] = 1;        }            for (int i = n-1; i >0; i--)            {                for (int j = i + 1; j <= n; j++)                {                    dp[i][j] = dp[i + 1][j] + 1;                    for (int k = i; k <=j; k++)                    {                        if (a[i] == a[k])                            dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j]);                    }                }            }        cout << "Case "<<++cnt<<": " << dp[1][n] << endl;;    }    return 0;}
         
        
       
      
     

NYOJ 746  整数划分

emmmm……都写到注释里了，，，（自己还是写不出来，，，还是要看别人的题解orz，不要方！人一我百，人十我万！早晚会写出来的）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;int n,t,m;ll a[25][25];ll dp[25][25];//表示到i为止，填j个乘号的最大值string s;int main(){    cin >> t;    while (t--)    {        cin >> s>>m;        m--; //拆分为m组数的乘积，添加m-1个*        n = s.length();        for (int i = 0; i < n; i++)  //字符串转换为数        {            a[i][i] = s[i] - '0';            for (int j = i + 1; j < n; j++)                a[i][j] = a[i][j - 1] * 10 + s[j] - '0';        }        memset(dp, 0, sizeof(dp));        for (int i = 0; i < n; i++) //初始化dp，dp[i][0]→不添*→a[0][i]            dp[i][0] = a[0][i];        for (int j = 1; j <= m; j++) //枚举添*的个数            for (int i = j; i < n; i++)  //添加j个*至少有i+1个数，i+1个数有i个间隔，所以初始条件为i=j（此处s下标是从0开始的）                for (int k = 0; k < i; k++)//枚举*添加的位置                    dp[i][j] = max(dp[i][j], dp[k][j - 1] * a[k+1][i]); //最优解为此时dp[i][j]和添加j-1个*时的dp[k][j-1]与末尾数值的乘积        cout << dp[n-1][m] << endl;    }    return 0;}
         
        
       
      
     

 hdu 4238 You are the one

dp[i][j]：i~j的最优解（不考虑i之前和j之后的人，只考虑[i,j]）

递推公式：dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]+d[i]*(k-i)+(sum[j]-sum[k])*(k-i+1));

                  把黑屋子看成栈，对于每个区间[i,j]，考虑将i扔到黑屋子里去~然后枚举出栈的位置~

                   i处进栈k处出栈，上台顺序就变为i+1,i+2......i,k+1,k+2.....j最优为min(dp[i+1][k]+dp[k+1][j]+d[i]*(k-i)+(sum[j]-sum[k])*(k-i+1));

                   //只考虑[i,j],看成把i~j单独拿出来的子列                                                                                ↑i前面有(k-i)个人  ↑k+1~j前面有(k-i+1)个人

#include
     
      #include
      
       #include
       
        using namespace std;int t,dp[105][105],d[105],n;int sum[105];int main(){    cin >> t;    for (int m = 1; m <= t; m++)    {        memset(dp, 0, sizeof(dp));        cin >> n;        sum[0] = 0;        for (int i = 1; i <= n; i++)        {            cin >> d[i];            sum[i] = sum[i - 1] + d[i];        }        for(int l=1;l
       
      
     

 hdu 2476

#include
     
      #include
      
       #include
       
        using namespace std;int dp[105][105];int ans[105];string s, t;int main(){    while (cin >> s)    {        cin >> t;        int len = t.length();        memset(dp, 0, sizeof(dp));        for(int j=0;j
        
         =0;i--)            {                dp[i][j] = dp[i + 1][j] + 1;                for (int k = i+1; k <= j; k++)                    if(t[i]==t[k])                    dp[i][j] = min(dp[i][j], dp[i+1][k] + dp[k + 1][j]);            }        }        for(int i=0;i