再帰、DP、法則性の3通りで343. Integer Break

Integer Break - LeetCode
Can you solve this real interview question? Integer Break - Given an integer n, break it into the sum of k positive inte...

Solution が無かったので自分の解法。

再帰

まずは具体例で考える。

n=10の場合、1と9に分けられる。9はさらに2と7、7はさらに3と4・・・というように樹形図のように分岐していく。

ある値numは、iとnum-iに分割でき、この分割を繰り返し適応できる。

これらの木を全探索し、最大値を返せば答えになる。

メモ化することで計算量はO(N)となる。

from functools import lru_cache

class Solution:
    def integerBreak(self, n: int) -> int:

        @lru_cache(maxsize=None)
        def dfs(num):
            if num == 1:
                return 1
            
            maxVal = 0 if num == n else num
            
            for i in range(1,num):
                val = dfs(i) * dfs(num-i)
                maxVal = max(maxVal, val)
            
            return maxVal
        
        ans = dfs(n)
        
        return ans
                

入力されるnは必ず分割しなければならないため、maxValの初期値は0になる。

1度でも分割してしまえば、分割せずに自分自身の値の方が大きくなる可能性もあるため、maxValの初期値はnumで開始する。

DP

再帰の解法のアイデアに似ているが、ある値が与えられた時、分割したほうが大きな値を得られる場合もあるし、自分自身をそのまま使う方が大きな値になる場合もある。

このアイデアをりようし、DPテーブルを更新していく。

dp[i]は、iを入力した時に得られる最大の積。

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n+1)
        dp[2] = 1
        
        for i in range(1, n+1):
            for j in range(1, i+1):
                if i+j>n:
                    continue
                
                x = max(i, dp[i])
                y = max(j, dp[j])
                dp[i+j] = max(dp[i+j], x * y)
        
        return dp[n]

計算量はO(N^2)。

法則性

まずは10ぐらいまで手作業で実験してみる。

2 : 1x1=1
3 : 1x2=2
4 : 2x2=4
5 : 2x3=6
6 : 3x2x2=9
7 : 3x4=12
8 : 2x3x3=18
9 : 3x3x3=27
10: 3x3x2x2=36

出来るだけ2と3に分割した方が答えに近づきそうな法則が得られた。

できるだけ3を使うようにしたいので、3で割った商と余りがキーとなる。

余りが0の場合、全て3に分割出来るので全部掛け算する。

余りが1の場合、3x1よりも2x2の方が値が大きくなってしまう。

1個の3と余り1を2x2に分割するため、n // 3 – 1個の3を使う。

余りが2の場合、そのまま掛け算すれば最大になる。

mod 3で場合分けしていく都合、3以下の値はコーナーケースとなるので個別に対処して完成。

class Solution:
    def integerBreak(self, n: int) -> int:
        if n == 2:
            return 1
        if n == 3:
            return 2
        
        if n % 3 == 0:
            ans = 3 ** (n // 3)
        elif n % 3 == 1:
            ans = 3 ** (n // 3 - 1)
            ans *= 4
        else:
            ans = 3 ** (n // 3)
            ans *= 2

        return ans

コメント

タイトルとURLをコピーしました