算法一:区间dp
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 310;
int n;
int a[N],s[N],f[N][N];
int dp(int x,int y)
{
if(x==y)return 0;
if(f[x][y]!=-1)return f[x][y];
f[x][y]=1e8;
for(int k=x;k<=y-1;k++)
{
f[x][y]=min(f[x][y],dp(x,k)+dp(k+1,y)+s[y]-s[x-1]);
}
return f[x][y];
}
int main()
{
cin>>n;
for(int i =1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
}
memset(f,-1,sizeof f);
cout<<dp(1,n);
return 0;
}
算法二:记忆化搜索
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 310; // 定义最大石子堆数
int n; // 石子堆数
int a[N], s[N], f[N][N]; // a数组存储每堆石子的数量,s数组存储前缀和,f数组用于记忆化
// dp函数用于计算合并石子堆x到y的最小代价
int dp(int x, int y)
{
if (x == y) return 0; // 如果只有一堆石子,不需要合并,代价为0
if (f[x][y] != -1) return f[x][y]; // 如果这个子问题已经解决过,则直接返回存储的结果
f[x][y] = 1e8; // 初始化当前子问题的代价为一个很大的数
// 遍历所有可能的分割点k,尝试分割成两部分,并递归计算最小代价
for (int k = x; k <= y - 1; k++)
{
f[x][y] = min(f[x][y], dp(x, k) + dp(k + 1, y) + s[y] - s[x - 1]);
}
return f[x][y]; // 返回合并石子堆x到y的最小代价
}
int main()
{
cin >> n; // 读入石子堆数
for (int i = 1; i <= n; i++)
{
cin >> a[i]; // 读入每堆石子的数量
s[i] = s[i - 1] + a[i]; // 计算前缀和,s[i]存储前i堆石子的总数
}
memset(f, -1, sizeof f); // 初始化记忆化数组为-1
cout << dp(1, n); // 输出合并所有石子堆的最小代价
return 0;
}