最佳加法表达式 DP
题意：
有一个由1..9组成的数字串.问如果将m个加号插入到这个数字串中,在各种可能形成的表达式中，值最小的那个表达式的值是多少。 输入： 5 3 1 2 3 4 5 输出： 24
核心内容总结：所谓的DP是指 从最小的子结构最优，推往全局的过程。
跟是不是递推或者dfs还是记忆化无半毛钱关系。
重剑无锋大巧不工，贵在领悟精神。
今天写这篇主要是为了总体的认识一下DP。
DP是什么呢：说白了就是一个找最优子结构的过程，至于愿怎么找，那就随意了。
但说白了核心还是通过遍历（暴力，怎么暴力怎么来）来找各个最优子结构，由最小的局部最优推至全局。
其实拿for循环，循环套循环和dfs都一样，其实都是从最局部最小的问题最优，推至全局最优。
综上总结：1.递推（自底向上法） 2.递归（带备忘的自顶向下法） 其实都是一种东东。
这道题比较典型，就拿这道题为例吧！
在10个数字中放任意个加号使得组成的表达式的和最小。
状态转移方程：
将m个加号插入到n个数字组成的数字串中
V(m,n) 表示将m个加号插入到n个数字组成的数字串中组成的表达式和最小的表达式
i表示在第i个数后面插入加号
V(m,n) = Min{ V(m-1,i) + Num(i+1,n) } ( i = m … n-1)
表达式的最后一个加号添加在第 i 个数字后面
这个i要试遍所有的情况
1.先写一下裸跑dfs，由于不用记忆化，新手的话比较容易理解。
坏处是不开记忆化单纯费时间，因为暴搜的过程中产生了许多冗余的搜索。
好处是不开的话，省下了记忆各个最优子结构的内存。
具体取舍，开还是不开根据实际情况来定。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF = 99999999;
int a[1005],num[1005][1005];
int V(int m,int n)
{
if(m == 0)//无加号
return num[1][n];
else if(n < m+1)//加号过多
return INF;
else
{
int t = INF;
//这里有点像回溯，回溯的话递归里面有循环
//说说实话，递归真的很简单，就是把递推公式写进来
for(int i = m;i <= n-1;i++) //这里是n减一，排除了最后一个数字后面放加号的情况
t = min(t, V(m-1,i)+num[i+1][n]);
//不懂的位置画个实例，会很简单，因为熟悉，所以容易
return t;
}
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
for(int i = 1;i <= n;i++)
scanf("%d",&a[i]);
//预处理,计算i到j数字串组成的数字
for(int i = 1;i <= n;i++)
{
num[i][i] = a[i];//只有一个数字
for(int j = i+1;j <= n;j++)
{
//这个表达式也可以好好看一下
num[i][j] = num[i][j-1]*10 + a[j];
}
}
cout<< V(m,n) <<endl;
}
return 0;
}2.记忆化搜索
int V(int m,int n) {
if(v[m][n]!=0)return v[m][n];
for(int i = m;i <= n-1;i++)
t = min(t, V(m-1,i)+num[i+1][n]);
return v[m][n]=t;
}
既然已经知道当前子结构的最优情况，爆破再遇见时就不用再扫一遍了。
所以因为少扫了很多东西，所以很省时间。
但也得开内存去存各个子结构的最优情况！！！#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF = 99999999;
int a[1005],num[1005][1005];
int v[1005][1005];
int V(int m,int n)
{
int t = INF;
if(v[m][n]!=0)return v[m][n];
if(m == 0)//无加号
return num[1][n];
else if(n < m+1)//加号过多
return INF;
else
{
//这里有点像回溯，回溯的话递归里面有循环
//说说实话，递归真的很简单，就是把递推公式写进来
for(int i = m;i <= n-1;i++) //这里是n减一，排除了最后一个数字后面放加号的情况
t = min(t, V(m-1,i)+num[i+1][n]);
//不懂的位置画个实例，会很简单，因为熟悉，所以容易
}
return v[m][n]=t;
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
for(int i = 1;i <= n;i++)
scanf("%d",&a[i]);
//预处理,计算i到j数字串组成的数字
for(int i = 1;i <= n;i++)
{
num[i][i] = a[i];//只有一个数字
for(int j = i+1;j <= n;j++)
{
//这个表达式也可以好好看一下
num[i][j] = num[i][j-1]*10 + a[j];
}
}
cout<< V(m,n) <<endl;
}
return 0;
}3.自下而上的递推 也就是一般而言的DP
留意一下，确实是 i=1，j=i，k=i开始扫的
利用for循环遍历所有情况，而且是自底向上，通过最小单位的子结构 来推往全局的。
for(int i=1;i<=m;i++)
for(int j=i;j<=n;j++)
for(int k=i;k<=j;k++)#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1005;
int a[N],num[N][N],dp[N][N];
//a[N]里面是存数字串
//num[i][j]表示数字串a[N]的第i位到第j位之间的数字串表示的数组
//dp[i][j]在i个数字中插入j个加号所能形成的表达式最小值
int main(){
int n,m;
while(scanf("%d %d",&n,&m)){
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
//预处理,计算i到j数字串组成的数字
for(int i=1;i<=n;i++){
num[i][i]=a[i];//只有一个数字
for(int j=i+1;j<=n;j++){
num[i][j]=num[i][j-1]*10+a[j];
}
}
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++){
dp[0][i]=num[1][i];//无加号时
}
//其实就是感觉在那个位置放不放加号
//这里n可以写在m前面。要加一个限制条件n>m，好麻烦，所以m在前且n=m+1
//这里k的取值范围就是m到n，k表示在第k个数后面插入加号
for(int i=1;i<=m;i++)
for(int j=i;j<=n;j++)
for(int k=i;k<=j;k++)
dp[i][j]=min(dp[i][j],dp[i-1][k]+num[k+1][j]);
cout<<dp[m][n]<<endl;
}
}