آیا گامی در راه پله بازگشتی خود ندارید؟

مشکل راه پله بازگشتی مقدمه ای کلاسیک برای برنامه نویسی پویا است و یکی از بسیاری از مراحل برای صعود به آن حالت خوشحال به نام تفکر الگوریتمی است.

مشکل به شرح زیر است:

با توجه به یک عدد صحیح

n

نمایانگر یک راه پله با تعداد زیادی از پله ها و محدودیتی که می توانید همزمان از آن فقط 1 یا 2 پله بالا بروید ، پیدا کنید که چند راه منحصر به فرد برای بالا رفتن از آن وجود دارد.

به عنوان مثال ، چه زمانی

n = 2

، باید 2 مورد را برگردانید زیرا برای رسیدن به بالا 2 راه وجود دارد:

1. 1 مرحله + 1 مرحله
2. 2 مرحله

توضیحات زیادی در مورد این مسئله وجود دارد – من فیلم YouTube YouTube CS Dojo را توصیه می کنم ، جایی که او نیمه اول فیلم 20 دقیقه ای را صرف توضیح بصری مشکل (با جزئیات بسیار زیاد) می کند و نیمه دوم راه های مختلفی برای حل آن را نشان می دهد.

پس از تماشای آن ، این مسئله را درک کردم ، اما شهود من هنوز در مورد آن وجود نداشت ، بنابراین به روش فاینمن درک خود را از آن دوباره برای شناسایی قطعات گمشده (ugh) انجام دادم.

در هسته اصلی خود ، راه حل نیاز دارد که شما رابطه بازگشتی را درک کنید تعداد راههای مرحله فعلی = تعداد راههای مرحله بعدی بعلاوه مرحله بعد از آن.

به عبارت دیگر:

خرید چرا؟ چرا مشخصاً 1 و 2؟

این قطعه گمشده بود.

در ویدئو ، YK