C++解最佳加法表达式动态规划递推，递归两种方法

电玩女神 2022-01-27 04:07 203阅读 0赞

### 最佳加法表达式（动态规划） ###

题目：有一个由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\]\};不断往前推，直到遇到边界值可以进行计算。  
![解题思路][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70]

#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;
    	} 
    }

**更正：动态规划和递归不是一种东西！！！**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70]: /images/20220127/5435b201eb8f44c9905560926afe1cda.png