最佳加法表达式（二）

描述

给定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

样例输出

24

样例解释

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