基础区间dp

区间dp就是把问题转成有区间的动态规划问题；
这里给出两个基础的区间dp问题供出学者对比发现如何把问题转化
学习区间dp的入门是学会找左右端点，间断点和区间长度

question 1
一条直线上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请编辑计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。
Input
输入有多组测试数据。

每组第一行为n(n<=100)，表示有n堆石子，。

二行为n个用空格隔开的整数，依次表示这n堆石子的石子数量ai（0<ai<=100）

Output
每组测试数据输出有一行。输出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。 中间用空格分开。
Sample Input
3

1 2 3

Sample Output
9 11

 memset(dp,0,sizeof(dp));
       for(int len=2;len<=n;len++)//区间长度
       {
           for(int i=1;i<=n;i++)//区间左端点
           {
               int j=i+len-1;//右端点
               if(j>n) break;
               dp[i][j]=inf;
               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]);

question 2

The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the product of the number on the card taken and the numbers on the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row.

The goal is to take cards in such order as to minimize the total number of scored points.

For example, if cards in the row contain numbers 10 1 50 20 5, player might take a card with 1, then 20 and 50, scoring
10150 + 50205 + 10505 = 500+5000+2500 = 8000

If he would take the cards in the opposite order, i.e. 50, then 20, then 1, the score would be
15020 + 1205 + 1015 = 1000+100+50 = 1150.
Input
The first line of the input contains the number of cards N (3 <= N <= 100). The second line contains N integers in the range from 1 to 100, separated by spaces.
Output
Output must contain a single integer - the minimal score.
Sample Input
6
10 1 50 50 20 5
Sample Output
3650

memset(dp,0,sizeof(dp));
   for(int len=3;len<n;len++)//区间长度
   {
       for(int i=1;i<=n;i++)//区间左端点
       {
           int j=i+len-1;//区间右端点
           if(j>n) break;
           int dp[i][j]=inf;
           for(int k=i+1;k<j;k++)//间隔点，端点不可用
           {
               dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[k]*a[j]);//每次取不包含左右端点
           }
       }
   }