动态规划4--最佳加法表达式

一、心得

心得：
动态规划因为有递推表达式，所以一定可以写成递推和递归两种写法。
因为递推一定可以写成递归。

区别两种问题：

在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要试遍所有的情况

在10个数字中放5个加号使得组成的表达式的和最小。
这就分在哪个位置上面放加号或者不放加号，有点像背包问题
将m个加号插入到n个数字组成的数字串中
V(m,n) = Min{ V(m-1,n-1) , V(m,n-1) }

这里可以把dp中的两维变成1维么，不行，因为看这两维表示的意义
在n个数字中插入m个加号，每一个加号在n个数字中的位置任意

一种是在把m个加号插入n个数字中
循环先m再n
一种是在n个数字中插入m个加号
循环先n再m
都要保证n比m大，n可以取m+1
m写在n前面，n等于m+1，可以省掉一半的情况。写法方便。
i表示插入的位置，位置要在m和n中间
3个加号插入5个数字中间，i的取值3到5？？？？
这个好想：我3个加号插入5个数字中间，最后一个加号的取值肯定要保证之前两个加号最少所需的三个数字

确定递归方程中每一个变量的取值范围实在是重中之重

二、题目及分析

题意：
有一个由1..9组成的数字串.问如果将m个加号插入到这个数字串中,在各种可能形成的表达式中，值最小的那个表达式的值是多少。
输入：
5 3
1 2 3 4 5
输出：
24

假定数字串长度是n，添完加号后,表达式的最后一个加号添加在第 i 个数字后面，
那么整个表达式的最小值，就等于在前 i 个数字中插入 m – 1个加号所能形成的最小值，
加上第 i + 1到第 n 个数字所组成的数的值（i从1开始算）。

设V(m,n)表示在n个数字中插入m个加号所能形成
的表达式最小值，那么：
if m = 0
V(m,n) = n个数字构成的整数
else if n < m + 1
V(m,n) = ∞
else
V(m,n) = Min{ V(m-1,i) + Num(i+1,n) } ( i = m … n-1)
Num(i,j)表示从第i个数字到第j个数字所组成的数。数字编号从1开始算。此操作复杂度是O(j-i+1)
总时间复杂度：O(mn2) .（dp二维表已经加号的位置）

三、代码及结果

递推

 1 /*
 2 最佳加法表达式： 
 3 题意：
 4 有一个由1..9组成的数字串.问如果将m个加号插入到这个数字串中,在各种可能形成的表达式中，值最小的那个表达式的值是多少。
 5 输入：
 6 5 3
 7 1 2 3 4 5
 8 输出：
 9 24 
10  
11 */
12 /*
13 预处理和排序都能很好的减少耗时 
14 */ 
15 #include<iostream>
16 #include<cstdio> 
17 #include<cstring> 
18 #include<algorithm> 
19 using namespace std;
20 const int INF=0x3f3f3f3f;
21 const int N=1005;
22 int a[N],num[N][N],dp[N][N];
23 //a[N]里面是存数字串
24 //num[i][j]表示数字串a[N]的第i位到第j位之间的数字串表示的数组
25 //dp[i][j]在i个数字中插入j个加号所能形成的表达式最小值
26 int main(){
27     int n,m;
28     while(scanf("%d %d",&n,&m)){
29         for(int i=1;i<=n;i++){
30             scanf("%d",&a[i]);
31         }
32         //预处理,计算i到j数字串组成的数字 
33         for(int i=1;i<=n;i++){
34             num[i][i]=a[i];//只有一个数字 
35             for(int j=i+1;j<=n;j++){
36                 num[i][j]=num[i][j-1]*10+a[j];
37             } 
38         }
39         memset(dp,0x3f,sizeof(dp));
40         for(int i=1;i<=n;i++){
41             dp[0][i]=num[1][i];//无加号时 
42         }
43         //其实就是感觉在那个位置放不放加号 
44         //这里n可以写在m前面。要加一个限制条件n>m，好麻烦，所以m在前且n=m+1
45         //这里k的取值范围就是m到n，k表示在第k个数后面插入加号 
46         for(int i=1;i<=m;i++)
47             for(int j=i;j<=n;j++)
48                 for(int k=i;k<=j;k++)
49                     dp[i][j]=min(dp[i][j],dp[i-1][k]+num[k+1][j]); 
50         cout<<dp[m][n]<<endl; 
51     }
52 } 
53

递归

 1 /*  
 2 题意：
 3 有一个由1..9组成的数字串.问如果将m个加号插入到这个数字串中,在各种可能形成的表达式中，值最小的那个表达式的值是多少。
 4 输入：
 5 5 3
 6 1 2 3 4 5
 7 输出：
 8 24 
 9 子问题：将最后面的那个加号放在第i个数字的后面，计算前i个 
10 数字的最佳加法表达式 
11 状态：V(m,n)表示在n个数字中插入m个加号所能形成 
12 的表达式最小值 
13 */
14 //不懂的位置画个实例，会很简单，因为熟悉，所以容易 
15 /*
16 心得：
17 动态规划因为有递推表达式，所以一定可以写成递推和递归两种写法。
18 因为递推一定可以写成递归。
19 
20 区别两种问题：
21 
22 在10个数字中放任意个加号使得组成的表达式的和最小。
23 状态转移方程：
24 将m个加号插入到n个数字组成的数字串中
25 V(m,n) 表示将m个加号插入到n个数字组成的数字串中组成的表达式和最小的表达式
26 i表示在第i个数后面插入加号
27 V(m,n) = Min{ V(m-1,i) + Num(i+1,n) } ( i = m … n-1)
28 表达式的最后一个加号添加在第 i 个数字后面
29 这个i要试遍所有的情况
30 
31 
32 
33 在10个数字中放5个加号使得组成的表达式的和最小。
34 这就分在哪个位置上面放加号或者不放加号，有点像背包问题
35 将m个加号插入到n个数字组成的数字串中
36 V(m,n) = Min{ V(m-1,n-1) , V(m,n-1) }
37 
38 这里可以把dp中的两维变成1维么，不行，因为看这两维表示的意义
39 在n个数字中插入m个加号，每一个加号在n个数字中的位置任意
40 
41 一种是在把m个加号插入n个数字中
42 循环先m再n
43 一种是在n个数字中插入m个加号
44 循环先n再m
45 都要保证n比m大，n可以取m+1
46 m写在n前面，n等于m+1，可以省掉一半的情况。写法方便。
47 i表示插入的位置，位置要在m和n中间
48 3个加号插入5个数字中间，i的取值3到5？？？？
49 这个好想：我3个加号插入5个数字中间，最后一个加号的取值肯定要保证之前两个加号最少所需的三个数字
50 
51 确定递归方程中每一个变量的取值实在是重中之重
52  
53 */ 
54 #include<iostream>  
55 #include<cstdio>  
56 #include<algorithm>  
57 using namespace std;  
58 const int INF = 99999999;  
59 int a[1005],num[1005][1005]; 
60 int V(int m,int n)  
61 {  
62     if(m == 0)//无加号  
63         return num[1][n];  
64     else if(n < m+1)//加号过多  
65         return INF;  
66     else  
67     {  
68         int t = INF;  
69         //这里有点像回溯，回溯的话递归里面有循环 
70         //说说实话，递归真的很简单，就是把递推公式写进来 
71         for(int i = m;i <= n-1;i++) //这里是n减一，排除了最后一个数字后面放加号的情况 
72            t = min(t, V(m-1,i)+num[i+1][n]); 
73         //不懂的位置画个实例，会很简单，因为熟悉，所以容易 
74         return t;  
75     }  
76 } 
77 int main()  
78 {  
79     int n,m;  
80     while(~scanf("%d%d",&n,&m))  
81     {  
82         for(int i = 1;i <= n;i++)  
83             scanf("%d",&a[i]);  
84         //预处理,计算i到j数字串组成的数字  
85         for(int i = 1;i <= n;i++)  
86         {  
87             num[i][i] = a[i];//只有一个数字  
88             for(int j = i+1;j <= n;j++)  
89             {  
90                 //这个表达式也可以好好看一下 
91                 num[i][j] = num[i][j-1]*10 + a[j];  
92             }  
93         }  
94         cout<< V(m,n) <<endl;  
95     }  
96     return 0;  
97 }