leetcode 553. Optimal Division | 553. 最优除法（暴力递归-＞傻缓存）

拼搏现实的明天。 2022-08-28 10:59 85阅读 0赞

## 题目 ##

[https://leetcode-cn.com/problems/optimal-division/description/][https_leetcode-cn.com_problems_optimal-division_description]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

两个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];
        }
    }

[https_leetcode-cn.com_problems_optimal-division_description]: https://leetcode-cn.com/problems/optimal-division/description/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/7b8a1cc718b1446b88ec92b315564472.png