【Algorithms】動的計画区間DP

概説
区間DPとは,名前からも区間と密接に不可分であること,すなわち動的計画により区間上の最適解を求めるアルゴリズムであり,まずセル間でDPを行い最適解を得た後,セル間の最適解を用いて大区間の最適解を求めることが主な考え方である.
一般的なアルゴリズム形式
区間DPのアルゴリズムフォーマットは比較的固定されており、一般に配列dp[i][j]によって区間[i,j]内の最適解(具体的にはテーマによって定義される)が表され、その後、1つの整形k(i<=k)によって表される

for (int i = 1; i <= n; i++）                   //     1    

    dp[i][i] = x;                               // x     

for (int len = 2; len <= n; len++)              //      

{

    for (int i = 1, j = len; j <= n; i++, j++)  //  [i,j]

    {

        //DP    

    }

}

例題
質問Y:【ダイナミックプランニング】魔法石をマージ
時間制限:1 Secメモリ制限:64 MB
タイトルの説明
宇宙梯子のエネルギーガイドレールには、1,2,3,...,n(n≦100)の番号の魔法石が並んでいる.各魔法石には一定の数があり、例えば7つの魔法石があり、それぞれ13、7、8、16、21、4、18である.今、n山の魔法石を集めて山になります.集計の過程は、隣接する2つの魔法石を毎回1つにしか積み上げられないため、n-1回の集計を経て1つになり、上の7つの魔法石のように、複数の方法で1つにまとめることができ、その中の2つの方法は図のように示されている.(a)の集計代価が20+24+25+44+69+87=267(b)の集計代価が15+37+22+28+59+87=248であることは、異なるプロセスで得られる集計代価が異なることがわかります.ここで、集計代価を最小限に抑える合理的な方法をプログラミングしてください.
 
入力
第1の動作は整数nであり、1
 
しゅつりょく
整数、すなわち最小代価.
 
サンプル入力

7
13 7 8 16 21 4 18

 
サンプル出力

239

タイトルリンク:http://exam.upc.edu.cn/problem.php?cid=1428&pid=24
分析:
この問題は区間DPの古典的な例題石と同じように,n堆石を合併して最後の最小費用を求めるものである.
n堆石の合併を要求し、動的計画の思想に基づいて、私たちはそれをサブ問題n-1堆石の合併に分けることができ、サブ問題によって最適解を求めることによって最終的な最適解を一歩一歩導いて、私たちはまず2堆石の合併の費用を求めることができて、それから3堆石の合併は2堆石と別の堆石の合併に分解することができます.これにより,先に求めたサブ問題の最適解により,最終的にn堆石の合併に要する最小費用を求めることができる.
dp[i][j]をi番目の堆石からj番目の堆石への合併とすると、dp[i][j]はkによってdp[i][k]+dp[k+1][j]に分割できる問題となり、このときその状態遷移方程式を書くことができ、dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sumij)、sumijは区間[i,j]内の合併石の総費用となる.時間の複雑さを減らす(接頭辞と思想、空間取得時間を犠牲にする)ことができる.
コードは次のとおりです.

#include

using namespace std;
int dp[101][101];
int sum[101];
int main()
{
    int n,v[101];
    cin>>n;
    memset(sum,0,sizeof(sum));
    memset(dp,0x3F,sizeof(dp));
    for(int i=1;i<=n;i++){
        cin>>v[i];
        sum[i]=sum[i-1]+v[i];
        dp[i][i]=0;
    }
    for(int len=2;len<=n;len++){
        for(int i=1,j=len;j<=n;i++,j++){
            int sumij=sum[j]-sum[i-1];
            for(int k=i+1;k<=j;k++){
                dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k][j]+sumij);
            }
        }
    }

//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=n;j++){
//            printf("%15d",dp[i][j]);
//        }cout<