对于每个dp[i][j]，也可以通过枚举最后一个乘号的位置k，将问题分解为前k个字符插入j-1个乘号和后i-k个字符的乘积。状态转移方程为：
dp[i][j] = max(dp[i][j], dp[k][j-1] * int(num[k:i])) 
其中num是输入的数字串，int(num[k:i])表示从第k个字符到第i个字符组成的子串的数值（）

暴力不行（原因：若暴力枚举，时间复杂度为 O(40^6)=O(4,096,000,000)会TLE），所以选择dp。
状态定义：dp[i][j]表示前i个数分成j段（即需要j+1个*）的最大乘积。
状态转移：dp[i][j] = max(dp[k-1][j-1]*a[k][i], dp[i][j])，表示在第k-1和第k个数之间加上一个*得到的最大值，其中前k-1个数采用的是dp值，即被分为了j-1段后的最大值，而后面的数（从k到i）则视为一整个数，与前面的dp值相乘。遍历全部k的位置，取最大值即为 dp[i][j]。
此外，还需要使用高精度

乘积最大

思路

暴力不行（原因：若暴力枚举，时间复杂度为 O(40^6)=O(4,096,000,000)会TLE），所以选择dp。
状态定义：dp[i][j]表示前i个数分成j段（即需要j+1个*）的最大乘积。
状态转移：dp[i][j] = max(d

全部评论 2