最佳加法表达式（二）

描述展开目录

给定 n 个 1 到 9 的数字，要求在数字之间最多添加 m 个加号 (加号两边必须有数字），使得所得到的加法表达式的值最小，并输出该值。

输入展开目录

每组数据三行。第一行是整数 n，表示有 n 个数 (0<n≤10)
第二行是整数 m，表示可以使用 m 个加号
第三行有 n 个数 $a_i (1≤a_i~≤9)$

样例输入展开目录

5
3
1 2 3 4 5

样例输出展开目录

样例解释展开目录

12+3+4+5

解题思路展开目录

动态规划常规题目，首先声明数组下标均从 1 开始。

因为可能会用到数字中某一段的数据，比方说 234 或者 1234，所以用一个二维数组 num [][] 进行存储，表示从第 i 个数到第 j 个数的值为 numi，例如对于样例来说，num3=345

既然是动态规划，就要将中间值保存起来，所以用一个二位数组 res [][] 进行存储，表示前 i 个数中放 j 个加号的最小值为 resi，例如对于样例来说 res3=15，最终答案就应该是 resn

变量都定义完了，接下来就是算法思路。整个过程其实就是一个二重循环枚举数和加号的个数，那么就分三种情况：第一，加号个数等于 0，没有加号，那 resi=num1；第二，加号个数大于等于数的个数，假设当前枚举 s 个数，那么就一共有 s-1 个空隙可以插入加号，但是加号个数大于 s-1，结果肯定就有问题，加号多，对于这种情况我们直接将 res [i][j=INF；第三种情况，言外之意就是加号个数不等于 0 并且加号个数不大于数的空隙，对于这种情况我们就要再进行一重枚举，枚举放 1 个加号的时候，最小值是多少，枚举放 2 个加号的时候，最小值是多少，一直枚举到加号放万。

代码展开目录

import java.util.Scanner;

public class Main {
    static int n,m;//n个数字，m个加号
    static int arr[];
    static int num[][];//i到j的数字串
    static int min;//最小值
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        m = cin.nextInt();
        arr = new int[n + 1];
        num = new int[n + 1][n + 1];
        for(int i = 1;i <= n;i++) 
            arr[i] = cin.nextInt();
        //预处理数字串
        for(int i = 1;i <= n;i++) {
            num[i][i] = arr[i];
            for(int j = i + 1;j <= n;j++)
                num[i][j] = num[i][j - 1] * 10 + arr[j];
        }
        long[][] res = new long[n + 1][n + 1];//前i个数放j个加号的最小值
        for(int i = 1;i <= n;i++) {//枚举数
            for(int j = 0;j <= m;j++) {//枚举加号
                if(j >= i) //加号大于等于数的个数，∞
                    res[i][j] = Integer.MAX_VALUE;//非法状态
                else if(j == 0) //没有加号
                    res[i][j] = num[1][i];
                else {//能执行这里，表明j != 0 && i > j 意味着加号个数一定不比可放加号的位置多
                    long min = Integer.MAX_VALUE;
                    for(int k = 1;k <= j;k++)//枚举加号个数
                        min = Math.min(min,res[i - k][j - 1] + num[i - k + 1][i]);
                    res[i][j] = min;
                }
            }
        }
        System.out.println(res[n][m]);
    }
}

代码里面有一段是最重要的

min = Math.min(min,res[i - k][j - 1] + num[i - k + 1][i]);

这段代码表示的含义是：假设当前枚举到 k 个加号，那么此时最小值为 i-k 个数使用 j-1 个加号的加上剩下的后面一串数字串，也就是第 i-k+1 到 i 形成的数字串

举个例子，假设现在枚举到的 i 为 5，也就是前 5 个数，j 为 3，也就是 3 个加号，那么第一次执行更新 min 值的含义为：前 4 个数放 2 个加号的最小值加上 5 到 5 位置之间形成的数字串

第二次更新 min 值的含义为：前 3 个数放 2 个加号的最小值加上 4 到 5 位置之间形成的数字串

后面的更新都没有意义了，因为前 2 个数 2 个加号，也就是 res2 的值是 INF，一定不会更新 min

Catalog