بتل کد Battle Codeدارد باز می‌شود…

جواب «Cached Staircase» چالش 8 از جلسه‌ی 40

سؤال

تعداد راه‌های بالا رفتن از n پله را حساب کنید وقتی هر بار ۱، ۲ یا ۳ پله می‌توان رفت (ways(0) = 1 و برای n منفی صفر). تابع بازگشتی ways(n) را با @lru_cache(maxsize=None) کش کنید تا برای n بزرگ هم سریع باشد. n را بخوانید و تعداد راه‌ها و سپس ways.cache_info().misses را در دو خط چاپ کنید. برای 4:
7
7

راهنما

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)

اول خودت امتحان کن؛ جواب‌های دیگر هم قبول است. برگرد و خودت حلش کن