এবার তাহলে আমরা ন্যাপস্যাকের মত করে কাজ করব। একটা জায়গা আমি পরিষ্কার করতেও পারি, নাও করতে পারি। পরিষ্কার করলে এর পরে যেই জায়গাটা পরিষ্কার হয়নি, সেই জায়গাটা পরিষ্কার করতে চলে যাব এবং এক্ষেত্রে আমার একটা মুভ নষ্ট হবে। আর পরিষ্কার না করলে ঠিক পরের জায়গাটাতেই পরিষ্কার করতে চলে যাব। স্টেট থাকবে দুটো, dp(pos,k). কোন পজিশনে আছি ও কতবার পরিষ্কার করেছি। মুভ শেষ হয়ে গেলে কিংবা পজিশনের বাইরে চলে গেলে ০ রিটার্ন করব, অর্থাৎ এটাই হবে বেসকেস।