输入：partitions = [3, 8, 10] strLength = 20
输出：37
解释：切分顺序依次为10,3,8则为37
	 切分顺序依次为3,8,10则为49
	 切分顺序依次为10,8,3则为38
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

• 1
• 2
• 3
• 4
• 5

二、解题思路

​ 首先根据切点位置从小到大进行排序，为了便于计算需要加入切点位置0和字符串长度。如上列中排序并加入切点位置后数组为[0,3,8,10,20]。此题跟矩阵链乘法很相似，读者可以对比两题的解法。

1. 定义状态

​ 设dp[i][j]为第i个切点位置到第j个切点位置的最少切分花费，i和j从1开始计数，那我们最终要求出的是dp[1][partitions.length]即为切点位置partitions[1-1] = 0到 partitions[partitions.length -1]=20的最少切分费用。

​ 我么可以对dp[i][j]进行拆分，如果i和j满足j - i > 1时，则i和j中间必有一切点k,其切点k的位置在partitions[k-1]处，所以dp[i][j] = dp[i][k] + dp[k][j] + (partitions[j] - partitions[i])，其中partitions[j] - partitions[i]为在切点partitions[k-1]进行切分的花费，当然切点k可能出现多个，我们取最小花费那个。

2. 定义状态转移方程

当j - i <= 1时，有
​ $$dp[i][j]=0$$
否则
​ $$dp[i][j]=max(dp[i][k]+dp[k][j]+(partitions[j]-partitions[i]))$$

3. 初始化

​ 当j - i <= 1时，有$$dp[i][j]=0$$

4. 计算方式

​ 自底向上，自左向右计算。这里解释下是指dp二维表自底向上是指i从大往小计算，自左向右计算是指j从小到大计算。

三、代码实现

/**
 * 最小字符串划分问题
 *
 * @author hh
 * @date 2021-5-18 22:41
 */
public class MinStringPartition {

    public int minStringPartition(int[] partitions, int strLength, int[][] breaks) {
        int[][] dp = new int[partitions.length + 1][partitions.length + 1];
        //自顶向上，自左向右计算即可
        for (int i = partitions.length; i >= 1; i--) {
            for (int j = 1; j <= partitions.length; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                if (j - i <= 1) {
                    dp[i][j] = 0;
                    continue;
                }
                for (int k = i + 1; k < j; k++) {
                    int temp = dp[i][k] + dp[k][j] + partitions[j-1] - partitions[i-1] ;
                    if (dp[i][j] > temp) {
                        dp[i][j] = temp;
                        breaks[i][j] = k;
                    }
                }
            }
        }
        return dp[1][partitions.length];
    }

    public void print(int[] partitions ,int[][] breaks, int start, int end) {
        if (end - start >= 2) {
            System.out.print(partitions[breaks[start][end] - 1] + " ");
            print(partitions,breaks, start, breaks[start][end]);
            print(partitions,breaks, breaks[start][end], end);
        }
    }

    public static void main(String[] args) {

        int[] partitions = new int[]{0,3, 8, 10,20};
        int strLength = 20;
        int[][] breaks = new int[strLength + 1][strLength + 1];
        MinStringPartition minStringPartition = new MinStringPartition();
        System.out.println(minStringPartition.minStringPartition(partitions, strLength, breaks));
        minStringPartition.print(partitions,breaks,1,partitions.length);
    }
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">