این مساله و بسیاری از مساله های مشابه را میتوانیم با کشیدن یک جدول به صورت خیلی ساده حل کنیم. یک جدول به اسم $P$ با ۴ سطر (به تعداد سکه ها) و ۴۷ ستون ( به میزان بدهی) در نظر بگیرید. ابتدا سکه ها را به ترتیب از کوچک به بزرگ مرتب میکنیم و آن ها را با عدد های $i=1\ldots4$ شماره گذاری میکنیم. یعنی مثلا سکه سوم معادل ۱۰ سنتی خواهد بود

حال $P[i,j]$ (عدد نوشته شده در سطر $i$ و ستون $j$ ) را به عنوان «تعداد روشهای خرد کردن $j$ سنت بدهی، با سکه های اول تا $i$ ام» تعریف میکنیم. مثلا در سطر $i=3$ میخواهیم تعداد روشهای خرد کردن هر مبلغ (شماره ستون $j$ ) با ۳ سکه اول (۱، ۵ و ۱۰ سنتی) را محاسبه کنیم. به عبارت دیگر $P[3,27]$ معادل تعداد روشهای پرداخت ۲۷ سنت با سکه های ۱، ۵ و ۱۰ سنتی خواهد بود. توجه کنید هنگام محاسبه سطر $i$ مجاز به استفاده از سکه های بعدی نیستیم، یعنی مثلا در سطر $i=3$ نمیتوانیم ۲۵ سنتی استفاده کنیم.

چطور مقادیر جدول را محاسبه کنیم؟

فرض کنید بخواهیم مقدار $P[i,j]$ را محاسبه کنیم. دو حالت داریم:

1. اصلا از سکه $i$ ام استفاده نمی کنیم. در این حالت مساله مشابه وقتی است که میخواهیم $j$ سنت بدهی را فقط با سکه های $1\ldots i-1$ بپردازیم. لذا تعداد روشها برابر $P[i-1,j]$ خواهد بود.
2. از سکه $i$ ام هم استفاده میکنیم. فرض کنید ارزش سکه $i$ ام را $k$ بنامیم (مثلا برای $i=3$ خواهیم داشت $k=10$ سنت). چون مبلغی که میخواستیم بپردازیم $j$ سنت بود، وقتی از یک سکه $k$ سنتی استفاده کنیم باقیمانده مبلغ $j-k$ خواهد بود. از طرف دیگر برای پرداخت $j-k$ سنت همچنان میتوانیم از سکه $i$ ام استفاده کنیم. پس تعداد روشها در این حالت برابر $P[i, j-k]$ خواهد بود.

چون تعداد روشهای پرداخت $j$ سنت با $i$ سکه اول برابر مجموع حالات فوق است پس باید این دو مقدار را جمع کنیم، یعنی $P[i,j]=P[i-1,j]+P[i,j-k]$. نکته مهم: در تعریف حالت ها طوری عمل کردیم که هیچ روشی تکراری محاسبه نشود.

مثال

فرض کنید بخواهیم ۲۷ سنت را فقط با سه سکه اول (۱، ۵ و ۱۰ سنتی) بپردازیم. یا از سکه ۱۰ سنتی استفاده نمی کنیم: در این حالت مساله به پرداخت ۲۷ سنت بدهی فقط با دو سکه اول (۱ و ۵ سنتی) مبدل میشود. یا از سکه ۱۰ سنتی استفاده میکنیم: در این حالت $27-10=17$ سنت باقی می ماند، و میتوانیم برای پرداخت آن همچنان از سه سکه اول استفاده کنیم.

پس داریم: $P[3,27]=P[2,27]+P[3,17]$

پرکردن جدول

حال شروع به پر کردن جدول میکنیم. در سطر اول میخواهیم تعداد روشهای پرداخت مقادیر مختلف را تنها وقتی یک نوع سکه (۱ سنتی) داریم بشماریم، بدیهی است برای پرداخت $j$ سنت با سکه های ۱ سنتی تنها یک روش داریم (استفاده از $j$ سکه ۱ سنتی). پس مقادیر سطر اول همگی ۱ است.

حال سطر دوم (وقتی حداکثر از سکه ۵ سنتی استفاده میکنیم): برای مقادیر کمتر از ۵ سنت نمیتوانیم از سکه ۵ سنتی استفاده کنیم، پس باید مقادیر سطر قبل را در همین سطر هم کپی کنیم (یعنی ۴ عدد اول این سطر ۱ خواهد بود). برای پرداخت ۵ سنت دو حالت داریم: اگر از سکه ۵ سنتی استفاده نکنیم همان مقدار سطر قبل $P[1,5]$ خواهد شد. اما اگر از سکه ۵ سنتی استفاده کنیم یک روش داریم که کل آن را با یک سکه ۵ سنتی بپردازیم. پس P[2,5]=P[1,5]+1=2. به همین ترتیب مقادیر بالاتر را محاسبه میکنیم.

نهایتا جدول پر شده به صورت زیر خواهد بود:

پس تعداد راه حل های خرد کردن ۴۷ سنت با هر ۴ نوع سکه، ۳۹ است.

بیشتر بخوانیم

به همین کار ساده ای که خیلی راحت با قلم و کاغذ انجام دادیم «برنامه نویسی پویا» یا Dynamic Programming گفته میشه که یک روش الگوریتمی خیلی مهم و پر کاربرد برای حل کردن خیلی از مساله ها هست. مطالعه اون رو از کتابهای الگوریتمی نظیر مساله های الگوریتمی یا ترجمه کتاب مقدمه ای بر الگوریتمها یا از اینترنت شدیدا توصیه میکنم. بعضی از مساله های مرحله سوم (آزمون عملی) هم با این روش حل میشه.