می‌خواهیم از عدد $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$ را تولید کند.