---
title: "553. Optimal Division"
url: "https://laigary.com/interview/coding/553-optimal-division"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2023-01-29"
tags: ["Math"]
---

# 553. Optimal Division

[553\. Optimal Division](https://leetcode.com/problems/optimal-division/)

這是一題很有趣的題目，題目有動態規劃解法，但是我根本想不出來。

這也是一個多多觀察題目，我一開始也是想要去想要怎麼用動態規劃解，那就要想看看動態轉移方程式啦，題目想要找到怎麼把一連串相除的數字，可以任意加上合法的括號後，目標是要取得最大的值。

一開始想到「天啊！不但要找出要怎麼組合括號，回傳時還要把括號插入到正確的字串中，不能是直接算出答案」

我就先冷靜下來，觀察了一下，如果一連串數字相除，要取得最大值，需要有什麼條件？因為如果想不到條件，那就很拿觀察到子問題，也就很難用動態規劃做。

我觀察到的條件有

1.  要取得越大的值，一定是前半部分越大越好，後半部分越小越好。
2.  先看前半部分要怎麼越大越好？那就是除的次數越少越好，既然要越少越好，那是不是代表第一個數字一定要保留到最後除？例如：`100/(rest)` ，這樣處理好第一個問題了。
3.  後半部要怎麼越小越好？其實上面的敘述已經有一個結論了，既然要找最大的數字除的次數要越少，那除的次數越多，是不是數字會越小，而這個證明很簡單，一連串的數字只要沒有分數，那經過不斷不斷的相除，一定會是得到越小的數字，而且如果除數除的越小變成了一個分數，那被除數除出來的商還會更大！

所以結論就是，加括號的只有一種情況：`第一個數字（剩餘所有的數字）` 最後只要再處理兩個不會加括號的情況就好，那就是只要一個數字與只有兩個數字的情況。時間複雜度也是本題的最優解。

```python
class Solution:
    def optimalDivision(self, nums: List[int]) -> str:
        if len(nums) == 1:
            return str(nums[0])
        elif len(nums) == 2:
            return '/'.join(map(str, nums))
        else:
            return '{}/({})'.format(nums[0], '/'.join(map(str, nums[1:])))

```