题目：有一个由1…9组成的数字串.问如果将m个加号插入到这个数字串中,在各种可能形成的表达式中，值最小的那个表达式的值是多少?
动态规划：将问题拆分为规模更小的子问题，找出其动态转移方程、边界条件。
思路1：运用递推的方法，将m个加号插入到n个数字串里，不断将规模变大，**从边界出发,直到求出函数值，**下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解。V[m][n]=min{V[m-1][i]+num[i+1][n]};（i可取m~n-1,要通过循环遍历V[m-1][i]）//确定最右边的加号后，V[m][n]的最小值，即将m-1个加号插入前i个数字中所得到的最小值+i后面的数字。
#include<iostream> #include<cstring> using namespace std; int dp[1005][1005],NUM[1005][1005];//dp[m][n],m为加号，n为数字个数 int main(){ int num[1005],n,m; while(cin>>n>>m){ for(int i=1;i<=n;i++) cin>>num[i]; memset(dp,0x3f,sizeof(dp));//将dp初始化为最大值 //预处理 for(int i=1;i<=n;i++){ NUM[i][i]=num[i]; for(int j=i+1;j<=n;j++){ NUM[i][j]=NUM[i][j-1]*10+num[j]; } } //边界条件：不用插入加号的情况，dp等于数字串本身 for(int i = 1;i <= n;i++) dp[0][i] = NUM[1][i]; for(int i=1;i<=m;i++) for(int j=i;j<=n;j++) for(int k=i;k<=j;k++)//遍历dp，每一次取值与之前所得dp比较，取最小值。 dp[i][j]=min(dp[i][j],dp[i-1][k]+NUM[k+1][j]); cout<<dp[m][n]<<endl; } }思路2：运用递归的方法，从所求的位置出发，函数不断的向边界值靠拢。V[m][n]=min{V[m-1][i]+num[i+1][n]};不断往前推，直到遇到边界值可以进行计算。
#include<iostream> #include<cstring> using namespace std; const int Inf = 0x3f3f3f; int NUM[1005][1005],num[1005]; long long V(int m,int n){ if(m==0) return NUM[1][n]; else if(n<m+1) return Inf; else{ long long ans=Inf; for(int k=m;k<n;k++){ ans=min(ans,V(m-1,k)+NUM[k+1][n]); } return ans; } } int main(){ int n,m; while(cin>>n>>m){ for(int i=1;i<=n;i++) cin>>num[i]; //预处理 for(int i=1;i<=n;i++){ NUM[i][i]=num[i]; for(int j=i+1;j<=n;j++){ NUM[i][j]=NUM[i][j-1]*10+num[j]; } } cout<<V(m,n)<<endl; } }更正：动态规划和递归不是一种东西！！！
