每日小记-动态规划：怎么使用迭代公式构造循环次序：以最优除法为例
记录了啥
动态规划中
在拿到迭代公式之后(也就是知道了如何利用已知部分的信息求未知部分的信息之后)
怎么写循环（怎么循环，好在里面写迭代公式）
题目
最优除法https://leetcode-cn.com/problems/optimal-division/
简单说：一个数组全是正整数，从第一个到最后一个挨个除÷，也就是a/b/c/d/e....、y/z
求：在里面添加括号来改变运算次序，求出最大结果
这道题有最脑残的解法（妈的答案是固定，把第二个到最后一个括起来就行，我说我怎么效率那么低，3层循环的动态规划效率能高就tm见鬼了）
但是用来锻炼一下动态规划还是可以的
简单说，
要构造一个三维（lenlen4）的存储空间来存放辅助数组
其中ij位置记录从i到j的数能形成的最大值和最小值
这样，根据(n,m)和(m+1,p)的信息就能知道(n,p)的信息
//最初我考虑的遍历方式就是三层，外层i，中层j，内层枚举k，其中：i总结
动态规划的过程就是通过辅助空间记录之前求解过的过程，避免二次计算，
那么必须注意，如何安排循环方式使得在做某一次计算的时候，所需要的中间结果都是已经计算好的
本题我最初的考虑方式中，每一步求解时，都只知道了左段，不知道右段信息
因为我最外侧控制大的执行方向的变量是起始位置
而答案使用的是求解段的长度，这样长度从2开始增加，求解n长的时候，拆分的任何i，n-i两个段的信息都是求过的，已知的
直接贴代码吧
点击查看代码
public static String optimalDivision(int[] nums) {
int len=nums.length;
//后期为了字符串拼接方便啥的，可以考虑使用Stingbuffer
String[][][] maxMinString=new String[2][len][len];//最大值最小值对应的字符串
double[][][] maxMin=new double[2][len][len];//记录ij区间的公式的最大值和最小值
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if(i==j){
maxMin[0][i][j]=nums[i];
maxMin[1][i][j]=nums[i];
maxMinString[0][i][j]=String.valueOf(nums[i]);
maxMinString[1][i][j]=String.valueOf(nums[i]);
}else{
maxMin[0][i][j]=0;
maxMin[1][i][j]=10000;
}
}
}
//最初我考虑的遍历方式就是三层，外层i，中层j，内层枚举k，其中：imaxMin[1][i][k]/maxMin[0][k+1][i+c]){
maxMin[1][i][i+c]=maxMin[1][i][k]/maxMin[0][k+1][i+c];
//更新字符串记录，和括号，除号
//首先，两端的最值的字符串长成啥样都记录下来了，那么整体的最一下拼接就行了，但是要注意，右侧长度大于1时要套括号
if((i+c)!=(k+1)){
maxMinString[1][i][i+c]=maxMinString[1][i][k]+"/("+maxMinString[0][k+1][i+c]+")";
}
else{
maxMinString[1][i][i+c]=maxMinString[1][i][k]+"/"+maxMinString[0][k+1][i+c];
}
}
//更新最大值,左端最大值/右端最小值
if(maxMin[0][i][i+c]