[数据结构与算法]leetcode 553. Optimal Division | 553. 最优除法（暴力递归-＞傻缓存）

题目

https://leetcode-cn.com/problems/optimal-division/description/

题解

两个dp表相互依赖，没继续往后推自底向上的递归。

这题填dp的每一个位置都要O(n)，转换成自底向上的dp之后，可能会有斜率优化。

这么有趣的题，不知道为啥这么多人踩。。

class Solution {
    class Info {
        String exp;
        float value;

        public Info(String exp, float value) {
            this.exp = exp;
            this.value = value;
        }
    }

    public String optimalDivision(int[] nums) {
        // leftMax/rightMin
        Info[][] dpMax = new Info[nums.length][nums.length];
        Info[][] dpMin = new Info[nums.length][nums.length];
        Info info = processMax(0, nums.length - 1, nums, dpMax, dpMin);
        return info.exp;
    }

    public Info processMax(int L, int R, int[] nums, Info[][] dpMax, Info[][] dpMin) { // [L,R]闭区间
        if (L == R) {
            dpMax[L][R] = new Info(String.valueOf(nums[L]), nums[L]);
        } else {
            Info maxInfo = null;
            for (int M = L; M < R; M++) {
                Info leftMax;
                if (dpMax[L][M] != null) leftMax = dpMax[L][M];
                else leftMax = processMax(L, M, nums, dpMax, dpMin);

                Info rightMin;
                if (dpMin[M + 1][R] != null) rightMin = dpMin[M + 1][R];
                else rightMin = processMin(M + 1, R, nums, dpMax, dpMin);
                if (maxInfo == null || leftMax.value / rightMin.value > maxInfo.value) {
                    String rightExp = M + 1 == R ? rightMin.exp : "(" + rightMin.exp + ")";
                    maxInfo = new Info(leftMax.exp + "/" + rightExp, leftMax.value / rightMin.value);
                }
            }
            dpMax[L][R] = maxInfo;
        }

        return dpMax[L][R];
    }

    public Info processMin(int L, int R, int[] nums, Info[][] dpMax, Info[][] dpMin) {
        if (L == R) {
            dpMin[L][R] = new Info(String.valueOf(nums[L]), nums[L]);
        } else {
            Info minInfo = null;
            for (int M = L; M < R; M++) {
                Info leftMin;
                if (dpMin[L][M] != null) leftMin = dpMin[L][M];
                else leftMin = processMin(L, M, nums, dpMax, dpMin);

                Info rightMax;
                if (dpMax[M + 1][R] != null) rightMax = dpMax[M + 1][R];
                else rightMax = processMax(M + 1, R, nums, dpMax, dpMin);

                if (minInfo == null || leftMin.value / rightMax.value < minInfo.value) {
                    String rightExp = M + 1 == R ? rightMax.exp : "(" + rightMax.exp + ")";
                    minInfo = new Info(leftMin.exp + "/" + rightExp, leftMin.value / rightMax.value);
                }
            }
            dpMin[L][R] = minInfo;
        }
        return dpMin[L][R];
    }
}