DP N

隣接するものをくっつける

くっつける順番によってコストが異なる

コストを最小化する問題

領域を定義域とするDP

領域が指定された時のその領域をくっつける最安コストを値としてDP

code:python

def solve(N, XS):

@lru_cache(maxsize=None)

def sub(L, R):

if L == R:

return 0

ret = INF

for x in range(L, R):

v = sub(L, x) + sub(x + 1, R)

if v < ret:

ret = v

return sub(0, N - 1)

Cython

code:python

cdef sub(long L, long R):

cdef long long ret

if L == R:

return 0

if ret != 0:

return ret

ret = INF

for x in range(L, R):

v = sub(L, x) + sub(x + 1, R)

if v < ret:

ret = v

return ret

cdef solve(N, XS):

cdef long i

cdef long long v

v = 0

for i in range(N):

return sub(0, N - 1)