题意： 有一个由1..9组成的数字串.问如果将m个加号插入到这个数字串中,在各种可能形成的表达式中，值最小的那个表达式的值是多少。 输入： 5 3 1 2 3 4 5 输出： 24
今天写这篇主要是为了总体的认识一下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; } }
