设有一个长度为N的数字串，要求使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。

要用动态规划做。
问题中只有乘号插入的位置是变化的，取数字串中的任意一段（i到j）来考虑，若能求出在其中插入K-1个乘号的最大乘积，则只需穷举第K个乘号的插入位置t（t从初始的i+K-1开始插入，最多插入到j-1后）。该乘号把数字串分成了两段，前半段包含K-1个乘号（其最大值已经算出），将它的值与后半段的值相乘得到第K个乘号在位置t时的最大乘积。选出t在各个位置时得到的最大乘积即为问题的解。  
    依此类推，把K-1的问题归结为K-2的情况，……，直到求在任意一段中插入1个乘号的最大乘积时，需预先算出在任意一段中插入0个乘号时的最大乘积。而此时的值是已知的（即为该段的数值）。假设DP[i,j,K]表示在长为N的数字串中，从第i个数字到第j个数字之间插入K个乘号的最大乘积，动态转移方程如下：
DP[i,j,k] = MAX {DP[i,t,0] * DP[t,j,k-1] | i<t<j}