جواب «Cached Staircase» چالش 8 از جلسهی 40
سؤال
تعداد راههای بالا رفتن از n پله را حساب کنید وقتی هر بار ۱، ۲ یا ۳ پله میتوان رفت (ways(0) = 1 و برای n منفی صفر). تابع بازگشتی ways(n) را با @lru_cache(maxsize=None) کش کنید تا برای n بزرگ هم سریع باشد. n را بخوانید و تعداد راهها و سپس ways.cache_info().misses را در دو خط چاپ کنید. برای 4:77
راهنما
ways(n) = ways(n-1) + ways(n-2) + ways(n-3). هر مقدار متمایز n که واقعاً محاسبه شود یک miss است.
یک جواب درست
from functools import lru_cache
@lru_cache(maxsize=None)
def ways(n):
if n < 0:
return 0
if n == 0:
return 1
return ways(n - 1) + ways(n - 2) + ways(n - 3)
print(ways(int(input())))
print(ways.cache_info().misses)
اول خودت امتحان کن؛ جوابهای دیگر هم قبول است. برگرد و خودت حلش کن