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