区间dp暂时的理解

因为刚刚看了区间dp,所以写一下对区间dp的理解。

例题：

石子归并

看了一篇博客，觉得他说得比较容易理解，所以再次重复一遍：

假如你是上帝，已经知道了1~n堆石子的最优解，那么它肯定是由两个子堆组成的，

同理，两个子堆也分别都有自己的两个子堆，到最底层肯定是1~n堆石子的自身，

那我们回到最初，1~n堆石子肯定有一个分割点，

dp[ i ][ j ]代表 i 到 j 堆石子的最优解。dp[ 1 ] [ 5 ]=min{dp[1][1]+dp[2][5]+sum, dp[1][2]+dp[3][5]+sum, dp[1][3]+dp[4][5]+sum, dp[1][4]+dp[5][5]+sum};

就以上这么多种情况，以各个点为分界点，求出最小值(sum是价值，假设长度为1，2，3，4的最优解已经求出来了)

要注意的就是dp数组的初始化

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

int main()

{

    int n,dp[110][110],sum[110];

    while(~scanf("%d",&n))

    {

        memset(dp,0x3f3f3f,sizeof(dp));//注意初始化

        sum[0]=0;

        for(int i=1;i<=n;i++)

        {

            scanf("%d",&sum[i]);

            sum[i]+=sum[i-1];

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

        }

        for(int len=1;len<=n;len++)/*枚举“区间”长度*/

        {

            for(int i=1;i+len<=n+1;i++)/*枚举起点*/

            {

                int ends=i+len-1;/*终点*/

                for(int j=i;j<ends;j++)/*以j为分割点*/

                {

                    dp[i][ends]=min(dp[i][ends],dp[i][j]+dp[j+1][ends]+sum[ends]-sum[i-1]);

             //   printf("%d %d %d %d\n",len,i,j,ends);

                }

            }

        }

        printf("%d\n",dp[1][n]);

    }

    return 0;

}

巴特西

区间dp暂时的理解

石子归并

最新文章

热门文章