题目很简单,给出N个数字,不改变它们的相对位置,在中间加入K个乘号和N-K-1个加号,(括号随便加)使最终结果尽量大.因为乘号和加号一共就是N-1个了,所以恰好每两个相邻数字之间都有一个符号.例如:
N=5,K=2,5个数字分别为1,2,3,4,5,可以加成:
1*2*(3+4+5)=24
(1+2+3)*4*5=120
分析:用动态规划解决.设sum[i]为前i个数的总和,那么从j到k的总和为sum[k]-sum[j-1].设dp[i][j]表示前i个数中有j个乘号的最大的结果.则要想知道dp[i][j],可以尝试从第二个数的前面一直到最后一个数的前面依次添加乘号,将最大的结果保存至dp[i][j]中.就可以得到状态转移方程为:dp[i][j] = max(dp[i][j] dp[l-1][j-1] * (sum[i] - sum[l-1]));l为插入相乘的两个数的后一个数字的坐标.