می‌خواهیم از عدد ‎$1$‎ به عدد ‎$n$‎ برسیم. در هر مرحله می‌توانیم یا عددمان را دوبرابر کنیم یا به آن یک واحد اضافه کنیم. هزینه‌ی هر کدام از این دو عمل نیز ‎$1$‎ است.

به ازای هر عدد ‎$1 \leq x \leq n$‎ یک زیرمجموعه‌ی ‎$A_x$‎ از اعداد ‎$1‎, ‎2‎, ‎\dots‎, ‎x-1$‎ و یک عدد ‎$0 \leq c_x \leq 10$‎ نیز به ما داده‌اند که اگر در طول مراحل عدد ‎$x$‎ تولید شد و قبل از تولید ‎$x$‎ نیز حداقل یکی از اعضای ‎$A_x$‎ تولید شده بود ما باید هزینه‌ی اضافی ‎$c_x$‎ را بپردازیم. دقّت کنید که به‌ازای هر ‎$x$‎، ما هزینه‌ی ‎$c_x$‎ را حداکثر یک‌بار می‌پردازیم.

الگوریتمی چندجمله‌ای بر حسب ‎$n$‎ ارائه کنید تا با پرداخت کم‌ترین هزینه، با شروع از عدد ‎$1$‎، عدد ‎$n$‎ را تولید کند.

• سوال بعد
• سوال قبل