【dp】石子合并_无环

石子合并 （动态规划）
无环合并最小，只能相邻
状态转移方程： f[i][j] = min(f[i][k],f[k+1][j])+sum[i][j];
表示：从i到j 的最小合并值
动态规划意思是找到一个方程，然后可以从小一直推大，直到可知题目所求，所以从最小应有一个边界

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
int n;
int a[maxn];
int f[1000][1500]; // 
int sum(int l, int r)//求从l到r的每个石子的和
{
    int sum1 = 0;
    for(int i = l; i <= r; i ++)
    {
        sum1 += a[i];
    }
    return sum1;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
        {
            if(i == j)
            continue;
            else
            f[i][j] = 0x3f3f3f3f3f;
        }
    } //初始边界，如果i等于j则一个石子不用合并为0，因为要求最小，所以初始值应该最大

    for(int i = n; i >= 1; i --)//左边界
    {
        for(int j = i+1; j <= n; j ++)//右边界
        {
            for(int k = i; k < j; k ++)//中间k值
            {
                f[i][j] = min(f[i][k]+f[k+1][j]+sum(i,j),f[i][j]);
            }
        }
    }
    cout << f[1][n] << endl;
    return 0;
}