داینامیک نمایی:

گاهی اوقات در حل بعضی مسایل داینامیک خاص لازم می شود که تعداد متغیری بعد را نگه داریم. برای مثال در سوال ۳۱۰ سایت sgu مجبور می شویم از داینامیکی شبیه زیر استفاده کنیم:

d[i][a_1][a_2]...[a_m] =

تعداد حالات چیدن تخته ها هنگامی که فقط i تخته اول را تعیین کرده باشیم, در صورت ۱ بودن a_j تخته j ام از آخر آهنی باشد و در غیر این صورت چوبی باشد.

به طور کلی ما با این کار وضعیت m تخته آخر را نگه داشته ایم. در این صورت می توان آن را با حذف i امین تخته و شیفت دادن a_i ها از روی داینامیک های قبلی آپدیت کنیم.

اما نکته ای که وجود دارد این است که پیاده سازی چنین داینامیکی غیر ممکن است چون تعداد بعد های داینامیک باید ثابت باشد ولی در این سوال تعداد بعد ها به m وابسته است. راه حلی که وجود دارد این است که می توان تمام a_i ها را در یک بعد نگه داشت (در واقع فشرده کرد!). همانطور که می دانید‌ (!) متغیر ها در رم به صورت دنباله ای از ۰ و ۱ ذخیره می شود که در حالت عادی از معادل توان ۱۰ آن ها استفاده می شود ولی می توان با استفاده از اپراتور های بیتی از آن ها سوء استفاده (!) کرد و از آن به عنوان یک آرایه از ۰ و ۱ که طولش ۳۲ است (اگر int باشد)‌ استفاده کرد. در این جا نیز دنباله a را می توان در یک متغیر خلاصه کنیم به صورتی که a_i برابر رقم i ام آن متغیر در مبنای ۲ باشد. معمولا به چنین متغیری bit mask می گویند.

حال تعریف داینامیک این گونه می شود:

d[i][a_1][a_2]...[a_m] =

تعداد حالات چیدن تخته ها هنگامی که فقط i تخته اول را تعیین کرده باشیم, در صورت ۱ بودن بیت j ام mask تخته j ام از آخر آهنی باشد و در غیر این صورت چوبی باشد.

برای آپدیت کردن نیز می توان روی تخته n - m ام (تخته ای که در حالت کوچکتر وقتی i حذف می شود, به مجموعه m تخته آخر اضافه می شود) حالت بندی کرد:
اگر آهنی باشد:

d[i][(mask >> 1) + (1 << (m - 1))]

اگر چوبی باشد:

d[i][(mask >> 1)]

پس:

d[i][mask] = d[i - 1][(mask >> 1) + (1 << (m - 1))] + d[i - 1][(mask >> 1)]

دقت کنید که این فقط برای وقتی است که mask بیشتر از k تا بیت ۱ داشته باشد وگرنه d برابر ۰ می شود.

این سوال نمونه ساده ای از داینامیک نمایی بود. به طور کلی وقتی محدودیت های سوال کوچک باشد ولی نتوان جواب را مستقیم در آورد می توان با داینامیک به همین شیوه تمام حالات آن پارامتر را چک کرد و به جواب رسید.