Loading...
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
Solution が無かったので自分の解法。
再帰
まずは具体例で考える。
n=１０の場合、1と９に分けられる。９はさらに２と７、７はさらに３と４・・・というように樹形図のように分岐していく。
ある値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になる。
１度でも分割してしまえば、分割せずに自分自身の値の方が大きくなる可能性もあるため、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出来るだけ２と３に分割した方が答えに近づきそうな法則が得られた。
できるだけ３を使うようにしたいので、３で割った商と余りがキーとなる。
余りが０の場合、全て３に分割出来るので全部掛け算する。
余りが１の場合、３ｘ１よりも２ｘ２の方が値が大きくなってしまう。
１個の３と余り１を２ｘ２に分割するため、n // 3 – 1個の３を使う。
余りが２の場合、そのまま掛け算すれば最大になる。
mod 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
コメント