题目描述

282.石子合并
这道题是区间dp问题，因为题目是说相邻的石子合并有很强的阶段性，所以这道题需要用dp而不能用贪心算法，这道题f[i][j]表示的是从第i堆到第j堆的合成方式，属性是最小值，dp的第一层循环都是枚举长度 从len=2开始一直到第长度为n，第二层循环时开始的起点位置然后根据开始位置就能找出在这个长度下的末位置了，这个时候假设l到r，对于第三层的循环k的选择就是从l到r中找到一个合并点，因为两部分石子合并一定最后一次合并时两堆石子合并，假设这个点为k，则f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]), s[r]-s[l-1]时前缀和，因为要用到k+1，k+1<=r 所以循环中k<r,在开始的时候将f[l][r]设置为正无穷以便后续的操作而不能是初始中的0，最后输出f[1][n]即可

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 310;
int f[N][N];
int a[N],s[N];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]+=s[i-1]+a[i];
    }

    for(int len=2;len<=n;len++)
        for(int i=1;i+len-1<=n;i++)
        {
            int l=i; int r=i+len-1;
            f[l][r] =0x3f3f3f;
            for(int k=l;k<r;k++)
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        }
    cout<<f[1][n]<<endl;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla