今天看了某老师的dp视频 然后看到了这个题 当时跟嘴很厉害的翟**一起看 然后有点不明白 经过一番打斗后 终于搞明白。
题意：
有一个由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..9组成的数字串.问如果将m个加号插入到这个数字串中,在各种可能形成的表达式中，值最小的那个表达式的值是多少。 输入： 5 3 1 2 3 4 5 输出： 24 子问题：将最后面的那个加号放在第i个数字的后面，计算前i个 数字的最佳加法表达式 状态：V(m,n)表示在n个数字中插入m个加号所能形成 的表达式最小值 */ //不懂的位置画个实例，会很简单，因为熟悉，所以容易 /* 心得： 动态规划因为有递推表达式，所以一定可以写成递推和递归两种写法。 因为递推一定可以写成递归。 区别两种问题： 在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个数字中间，最后一个加号的取值肯定要保证之前两个加号最少所需的三个数字 确定递归方程中每一个变量的取值实在是重中之重 */ #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; 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; }
未完待续……