区间DP-NYOJ737石子合并

124 阅读 0 评论 82 点赞

我是靠谱客的博主昏睡啤酒，最近开发中收集的这篇文章主要介绍区间DP-NYOJ737石子合并，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

思路：

不管之前是多少个石子堆，最后都是变为两个，而这两个靠左合并或者靠右合并都是相同的，那么产生的子问题是，前i个和后n-i个堆合并，再逐步细分。

代码解释:

#include <iostream>
#include <stdio.h>
using namespace std;
int dp[1000][1000];
int a[1000];
int sum[1000];
int main()
{
    int n;
    while(cin>>n)
    {
    for(int i=1;i<=n;i++)
        {
        cin>>a[i];
        sum[i]=a[i]+sum[i-1];
        }
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
            dp[i][j]=(i==j?0:9999999);
    }
    for(int i=1;i<n;i++)<span style="white-space:pre">	</span>//这一步是n个石子，可以有1~n-1个间隔产生
    {
        for(int j=1;j<=n-i;j++) // 既然可以产生<em>i个间隔，j代表左侧从第几个开始产生子问题。</em>
        {
            for(int k=j;k<=i+j-1;k++)//K是从第j个到第i+j个，逐次更新，找到最优解，其中SUM代表了每次合并的石子总和
                dp[j][i+j]=min(dp[j][i+j],dp[j][k]+dp[k+1][i+j]+sum[i+j]-sum[j-1]);
        }
    }
    cout<<dp[1][n]<<endl;
    }
    return 0;
}

下面再给出个今后的模板代码：

#include <iostream>
#include <stdio.h>
using namespace std;
int dp[1000][1000];
int a[1000];
int sum[1000];
int main()
{
    int n;
    while(cin>>n)
    {
    for(int i=1;i<=n;i++)
        {
        cin>>a[i];
        sum[i]=a[i]+sum[i-1];
        }

    for(int x=0;x<n;x++)//这一步是n个石子，可以有0~n-1个间隔产生
    {
        for(int i=1;i<=n-x;i++) //表示从第i个开始
        {
            int j=i+x;<span style="white-space:pre">		</span>到第j个位置
            dp[i][j]=99999999;
            if(i==j)           
                dp[i][j]=0;
            for(int k=i;k<=j;k++)//K是从第i个到第j个，逐次更新，找到最优解，其中SUM代表了每次合并的石子总和
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
        }
    }
    cout<<dp[1][n]<<endl;
    }
    return 0;
}