ادعا می‌کنیم جواب بهینه‌ای وجود دارد که در آن اگر ‎$m$‎ پناهگاه و ‎$n$‎ آدم را بر حسب مکانشان مرتب کنیم و شماره‌گذاری کنیم، به ازای هر ‎$i$‎ خاصیت زیر برقرار است: ‎‎

• ‎ بین تمام آدم‌هایی که به ‎$i$‎ پناهگاه اول می‌روند کسی که بیش‌ترین ‎id‎ را دارد در نظر گرفته مثلا ‎$k$‎ می‌گوییم ‎$i$‎ پناهگاهی خوب است اگر و فقط اگر ‎$k$‎ نفر اول همه به ‎$i$‎ پناهگاه اول رفته باشند.

پس ادعا می‌کنیم جواب بهینه‌ای وجود دارد که در آن همه‌ی پناهگاه‌ها خوب‌اند. برای اثبات از برهان خلف استفاده کرده. جواب بهینه‌ای را در نظر بگیرید که بیش‌ترین پناهگاه خوب را دارد. اولین پناهگاه غیرخوب را ‎j‎ می‌نامیم و بزرگ‌ترین کسی که به ‎$j$‎ پناهگاه اول رفته را ‎$i$‎ می‌نامیم. بنابراین کسی وجود دارد قبل از ‎$i$‎ مثلا ‎$k$‎ که به پناهگاهی بعد از پناهگاه ‎$j$‎ رفته ‎$k<i$‎ و ‎$match[i] \leq match[j] < match[k ]$‎. ادعا می‌کنیم اگر جفت ‎$i$‎، ‎$k$‎ را با هم عوض کنیم جواب بهتر می‌شود. ‌با انجام این کار (اگر باز پناهگاه ‎$j$‎ خوب نبود با تکرار این عمل) بالأخره به حالتی می‌رسیم که پناهگاه ‎$j$‎ خوب شده و هیچ پناهگاهی بد نشده، بدیهی است که با این تغییر maxID‎ کسانی که به آن رفته اند کم‌تر شده و مسافت مجموع هم بیش‌تر نمی‌شود. و خوبیت باقی پناهگاه ها نیز عوض نمی‌شود‎. ‎ با توجه به لم بالا می‌توان به صورت پویا (داینامیک)‌ این مسئله را حل کرد. بدین صورت که ‎$DP[i][j]$‎ را برابر با جواب مسئله در صورتی که فقط ‎$i$‎ نفر اول و ‎$j$‎ پناهگاه اول وجود داشته باشند تعریف می‌کنیم. طبق لم بالا بدیهیست که کسانی که به پناهگاه آخر رفته اند می‌تواند ‎$k$‎ آدم آخر باشند‎ $k$)!‎ حداقل یک است). زیرا اگر این ‎$k$‎ تا متوالی از آخر نباشند خوبیت پناهگاه ‎$j-1$‎ از بین می‌رود. کافیست بر روی تعداد افرادی که در پناهگاه ‎$j$‎ ام رفته for‎ زده و اگر هزینه‌ی اینکه ‎$k$‎ نفر آخر در آن رفته باشند را ‎$Cost(k)$‎ بنامیم، در این صورت‎: ‎

‎$DP[i][j] = min_{k=1}^i(DP[i-k][j-1]‎ + ‎Cost(k))$ ‎

اما این الگوریتم از ‎$O(n^3)$‎ است که با روش زیر می‌توان آن را به ‎$O(n^2)$‎ کاهش داد. ‎$DPcomplete[i][j]$‎ حداقل هزینه که با ‎$i$‎ انسان اول ‎$j$‎ پناهگاه رو پوشوند که در هر پناهگاه ها حداقل یک نفر باشد و پناهگاه ‎$j$‎ ام خالی است. و ‎$DPtemp[i][j]$‎ حداقل هزینه که با ‎$i$‎ انسان اول ‎$j$‎ پناهگاه رو پوشوند که در هر پناهگاه‌ها حداقل یک نفر باشد و پناهگاه ‎$j$‎ ام می‌تواند خالی باشد‎.

‎ ‎$DPcomplete[i][j] = DPtemp[i-1][j]‎ + ‎Cost(i‎ -‎> j)$

‎ نفر ‎$i$‎ ام حتما باید به ‎$j$‎ برود حالا باید برای ‎$i-1$‎ نفر که پناهگاه ‎$j$‎ ام می تواند خالی باشد‎! ‎ ‎$DPtemp[i][j] = min(DPcomplete[i][j-1]‎ + ‎Cost(i‎ -‎> j-1)‎, ‎DPtemp[i-1][j-1]‎ + ‎Cost(i‎ -‎> j))$

‎ نفر ‎$i$‎ ام می‌تواند به ‎$j$‎ یا ‎$j-1$‎ برود‎. ‎

‎پيچيدگي

‎ مرتب کردن اعداد که از ‎$O(n \log n)$است!‎ حافظه داینامیک مورد نیاز هم از ‎$O(n^2)$‎ است و هر خانه آن از ‎$O(1)$‎ بروزرسانی می‌شود. پس پیچدگی کل الگوریتم (هم زمان هم حافظه) ‎$O(n^2)$‎ است‎!‎