世界上的人都变成废柴，这个世界就没有废柴了
区间DP
区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。
既然求解在一个区间上的最优解，那么把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的起点，自然终点也就明了了。然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。
代码语言：javascript复制memset(dp,0,sizeof(dp))//初始dp数组
for(int len=2;len<=n;len ){//枚举区间长度
for(int i=1;i<n; i){//枚举区间的起点
int j=i len-1;//根据起点和长度得出终点
if(j>n) break;//符合条件的终点
for(int k=i;k<=j; k)//枚举最优分割点
dp[i][j]=min(dp[i][j],dp[i][k] dp[k 1][j] w[i][j]);//状态转移方程
}
}优化
代码语言：javascript复制for(int len=2;len<=n;len )
{
for(int i = 1;i<=n;i )
{
int j = i len-1;
if(j>n) break;
for(int k = s[i][j-1];k<=s[i 1][j];k )
{
if(dp[i][j]>dp[i][k] dp[k 1][j] w[i][j])
{
dp[i][j]=dp[i][k] dp[k 1][j] w[i][j];
s[i][j]=k;
}
}
}
}Practice
石子合并
代码语言：javascript复制#include<iostream>
#include<algorithm>
#include<cstring>
#include <numeric>
using namespace std;
#define INF 0x3f3f3f3f
int a[400],b[400];
int dp[400][400];
int main()
{
int n ;
cin>>n;
memset(b,0,sizeof(b));
for(int i =1;i<=n; i)
{
cin>>a[i];
//前缀和
//b[i] = b[i-1] a[i];
}
//前缀和
partial_sum(a 1,a 1 n,b 1);
for(int len = 2 ;len<=n; len)//枚举长度
{
for(int i=1;i len-1<=n; i)//枚举起点
{
int l = i,r = len i-1;
dp[l][r] = INF;
for(int k = l;k<r; k)
{
dp[l][r] = min(dp[l][r],dp[l][k] dp[k 1][r] b[r]-b[l-1]);
//区间[l,r]的代价 = min(当前状态,区间[l,k]的代价 区间[k 1,r]的代价 [l,r]的代价和)
}
}
}
cout<<dp[1][n]<<endl;
system("pause");
return 0;
}HDU4283
代码语言：javascript复制#include<iostream>
#include<cstring>
using namespace std;
int a[110],b[110];
int dp[110][110];
int main()
{
int t;
cin>>t;
for(int num=1;num<=t; num )
{
int n;
cin>>n;
b[0] = 0;
memset(dp,0,sizeof(dp));
for(int i= 1;i<=n; i)
{
cin>>a[i];
b[i] = a[i] b[i-1];
}
for(int len=2;len<=n; len)
{
for(int i =1;i len-1<=n; i)
{
int l = i, r = len i-1;
dp[l][r] = 1e9;
for(int k=l;k<=r; k)
dp[l][r] = min(dp[l][r],dp[l 1][k] dp[k 1][r] (k-l 1)*(b[r]-b[k]) a[i]*(k-i));
}
}
//cout<<dp[1][n]<<endl;
printf("Case #%d: %dn",num,dp[1][n]);
}
return 0;
}POJ2955
括号最长匹配长度。
代码语言：javascript复制/*
用dp[l][r]表示区间[l,r]里最大完全匹配数。只要得到了dp[l][r]，那么就可以得到dp[i-1][j 1]
dp[i-1][j 1]=dp[i][j] (s[i-1]==s[j 1]？2:0).
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
ll dp[110][110];
char s[110];
int main()
{
while(cin>>s 1)
{
if(s[1] == 'e')
break;
memset(dp,0,sizeof(dp));
ll len = strlen(s 1);
for(int lenn = 1;lenn<=len; lenn)//枚举长度
{
for(int i =1;i lenn-1<=len; i)//枚举端点
{
int l = i,r = i lenn-1;
//如果知道了区间[l,r]的个数，那么很容易求出dp[l 1][r-1]的个数
if((s[l]=='('&&s[r]==')') || (s[l]=='['&&s[r]==']'))
dp[l][r] = dp[l 1][r-1] 2;
//枚举分界点
for(int k = l;k<r; k)
dp[l][r] = max(dp[l][r],dp[l][k] dp[k 1][r]);
}
}
cout<<dp[1][len]<<endl;
}
return 0;
}整数划分
代码语言：javascript复制题意：给出两个整数 n , m ,要求在 n 中加入m - 1 个乘号，将n分成m段，求出这m段的最大乘积
思路：这里给的乘号是有限个，所以状态方程里必须包含使用乘号的个数，此外还要包含区间长度。所以怎么用二维dp实现包含m和n，我们可以用dp[i][j]表示在第1~i个字符里插入j个乘号的最大值。
状态转移方程 dp[i][j]表示在第1~i个字符里插入j个乘号的最大值；用num[i][j]表示第i~j个字符表示的数字；
dp[i][j] = max(dp[i][j],dp[k][j-1]*num[k 1][i])/*
题意：给出两个整数 n , m ,要求在 n 中加入m - 1 个乘号，将n分成m段，求出这m段的最大乘积
思路：这里给的乘号是有限个，所以状态方程里必须包含使用乘号的个数，此外还要包含区间长度。所以怎么用二维dp实现包含m和n，我们可以用dp[i][j]表示在第1~i个字符里插入j个乘号的最大值。
状态转移方程 dp[i][j]表示在第1~i个字符里插入j个乘号的最大值；用num[i][j]表示第i~j个字符表示的数字；
dp[i][j] = max(dp[i][j],dp[k][j-1]*num[k 1][i])
*/
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
ll m;
char s[110];
ll dp[110][110];
ll num[110][110];
int main()
{
int t;
cin>>t;
while(t--)
{
memset(dp,0,sizeof(dp));
memset(num,0,sizeof(num));
cin>>s 1;
cin>>m;
int len = strlen(s 1);
for(int i =1;i<=len; i)
{
for(int j =i;j<=len; j)
{
num[i][j] = num[i][j-1]*10 (s[j]-'0');
}
}
for(int i=1;i<=len; i)
dp[i][0] = num[1][i];
for(int j =1;j<m; j)//插入第j个*
{
for(int i = 1;i<=len; i)
{
for(int k =1;k<i; k)
{
dp[i][j] = max(dp[i][j],dp[k][j-1]*num[k 1][i]);
}
}
}
cout<<dp[len][m-1]<<endl;
}
system("pause");
return 0;
}
