Форум » Динамическое программирование » №6502 не сходиться с ответом в чем моя проблема? » Ответить
№6502 не сходиться с ответом в чем моя проблема?
Razer133: не понимаю в чем проблема from functools import * @lru_cache(None) def f(n,e,k): if n>e or n==20 or n==58: return 0 if n==e: return k<=6 else: return f(n+1,e,k+1)+f(n+3,e,k)+f(n*3,e,k) print(f(3,37,0)*f(37,95,0)) ответ: 8684025 (правильный 365197)
Ответов - 2
Ж: Вы не учитываете, что при первом проходе до 37 уже несколько операций +1 было выполнено, поэтому при втором проходе их надо учесть. Вот рабочий код [pre2] f=lru_cache(10**5)(lambda n,n20_58,n37,k: \ f(n+1, n20_58 or n in [20,58], n37 or n==37,k+1)+\ f(n+3, n20_58 or n in [20,58], n37 or n==37,k)+\ f(n*3, n20_58 or n in [20,58], n37 or n==37,k)\ if n<95 else (n==95 and k<=6 and n20_58==False and n37)) print(f(3,False,False,0)) [/pre2]
Алексей21: Спасибо!
полная версия страницы