算法:最大算式问题
(最大算式)
For man is man and master of his fate
第一次看到这个题目，也是无从下手，但是初看一定是用dp动态规划没错，在借鉴了许多优质博客和自己实操之后，我对整个过程也有了自己的理解。
解法
首先我们可以这样子想，我们把前n个数中使用k个乘号来计算出最大值看作是一个过程，注意这里n的范围是(1-N)，k的范围是(1-K)，这样，我们每次进行一次计算最大值，都是解出全局最优解的一个子过程，并且我们可以使用这些计算出的子问题最优解，来进行下一次子过程的最优解运算，每一步在全局看来都是最好的决策，不难想出，当我们求到前N个数使用K个乘号这个子问题(最终一步)时，这个值已经是最优的了。
下面考虑如何实现，因为我今天只看明白了用dp数组来解(递归更简洁)，所以姑且就用这个方法叭，第一步，根据输入的N，K值，开一个dp数组，行数为(N+1)，列数为(K+1)，dp[i][j]的意思就是前i个数中使用j个乘号所能计算出的最大值，又因为i个数最多只能使用i-1个乘号，所以我们始终要保持i>j，所以下面黄***域是不用计算的，第二步，由于j为0时，我们无法使用乘号，所以dp[i][0]的最大值只能是前i个数的和，所以我们还要初始化第一列，如下图，以题目样本为例
这里dp[i][0]这一列都初始化好了，代表不使用乘法符号时，前i个数所能计算出的最大值，接下来我们计算下一列
当我们计算dp[2][1]这个位置时，我们此时有两个数，一个乘号可以用，所以无论如何，这个乘号都要用掉，故dp[2][1]=2
接下来计算dp[3][1]，此时我们面临两决策，即使用前两个数的积加上第三个数的和作为解，还是使用第一个数与后两个数的积的和作为解，这就是个问题，用公式表达就是
dp[3][1] = Max(dp[2][0] * (dp[3][0]-dp[2][0])，dp[1][0] * (dp[3][0]-dp[1][0]))
这里可以计算出dp[3][1]的最优值是9
这个确实挺绕的，不过没关系，我来继续讲解，下面我们计算dp[4][1],根据上面的思路，这次公式变为
dp[4][1] = Max(dp[3][0] * (dp[4][0]-dp[3][0])，dp[2][0] * (dp[4][0]-dp[2][0])，dp[1][0] * (dp[4][0]-dp[1][0]))，这回dp[4][1]的最优解是24
同理，我们接着来看dp[5][1]，此次公式变为
dp[5][1] = Max(dp[4][0] * (dp[5][0]-dp[4][0])，dp[3][0] * (dp[5][0]-dp[3][0])，dp[2][0] * (dp[5][0]-dp[2][0])，dp[1][0] * (dp[5][0]-dp[1][0]))，这次的最大值是54
此时，貌似我们发现了规律，从dp[2][1]一直计算到dp[5][1]，整个过程貌似在同一个循环里，这样可以推算出状态转移方程
dp[i][j] = Math.max(dp[i][j],dp[p][j-1] * (dp[i][0]-dp[p][0]));(1<=p<i)
这样，根据这个递推公式，我们就可以计算dp中剩下的数，最终的最优解就是dp[N][K]，为120
而对于dp[i][j]的计算，由于dp是一个二维表格，所以dp[i][j]的遍历还要套两层for循环，上code
package 蓝桥;
import java.util.Scanner;
public class 最大算式 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();//输入数字的数目 (1~N)
int K = in.nextInt();//出现的乘号数目
int[][] dp = new int[N+1][K+1];//dp[i][j]表示前i个数组成的式子使用j个乘号可以得到的最大值
//初始化dp的第一列，因为当使用的乘号数目为0时，dp[i][j]只能在使用加号的时候才能获得最大值
int sum = 0;
for(int i=1;i<=N;i++) {
int input = in.nextInt();
sum+=input;
dp[i][0] = sum;//dp数组第一列已经初始化好
}
System.out.println(getMax(dp, N, K));
}
static int getMax(int[][] dp,int N,int K) {
//注意，dp数组的遍历是按每一列每一列来的
for(int j=1;j<=K;j++) {
for(int i=2;i<=N;i++) {
if(i>j) {//因为i个数中最多能使用i-1个乘号，所以为了加速dp的遍历，剪枝
for(int p=1;p<i;p++) {
dp[i][j] = Math.max(dp[i][j],dp[p][j-1]*(dp[i][0]-dp[p][0]));//状态转移方程
}
}
}
}
return dp[N][K];
}
}
