Mr. Hikiko and a Strange Game (Easy)

এই সমস্যাটি ডায়নামিক প্রোগ্রামিংয়ের মাধ্যমে সমাধান করা যেতে পারে। ধরি DP[i][j] হচ্ছে সর্বোচ্চ পয়েন্ট আমরা পাবো 1 থেকে i সারি পর্যন্ত, যদি আমরা ith সারির জন্য jth থেকে (j + k - 1)th ঘর গুলো সিলেক্ট করি। যেহেতু আমরা l এর চেয়ে বেশি ব্যাবধান এর কোনো লাফ দিতে পারি না এবং যদি আমরা এই সারির এই ঘরগুলো নিতে চাই , তাহলে আমাদেরকে (i - 1)th সারির এমন একটা ঘর থেকে লাফ দিয়ে আসতে হবে যেনো ব্যাবধান l এর বেশি না হয়। তাহলে আমরা দেখতে পাই যে,

DP[i][j] = max(DP[i - 1][x]) (here, j - l - k + 1 ≤ x ≤ j + k + l - 1) + sum(points[i][j] + . . . + points[i][j + k - 1]).

আর, উত্তর হবে DP[i] এরের ভ্যালুগুলোর মধ্যে সর্বোচ্চ। টাইম কমপ্লেক্সিটি O(nm2)।

আমরা সহজ ভার্সন এর প্রবলেম টা এই টাইম কমপ্লেক্সিটিতে করতে পারবো, কিন্তু কঠিন ভার্সন এর টা করতে আমাদের O(nm) কমপ্লেক্সিটির কোনো সমাধান এ আসা লাগবে। এজন্য আমাদের এমন একটা ডাটা স্ট্রা্কচার ব্যাবহার করতে হবে, যেন আমরা DP[i - 1][x] এর ভ্যালুগুলোর সর্বোচ্চটা মেন্টেইন করতে পারি। এক্ষেত্রে আমরা ডিকিউ এর মাধ্যমে স্লাইডিং উইন্ডো টেকনিক টা ব্যাবহার করতে পারি। এটা সম্পর্কে বিস্তারিত জানতে এই লেখা বা এই লেখাটা পড়োতে পারো।