DP trick - Knuth's optimization

কিছু classical dp problem আছে "cutting rod" এর মত যেখানে আমাদের একটা গ্রুপ এর মধ্যে ম্যাস্কিমাম বা মিনিমাম ভ্যালু বের করতে হয় । প্রবলেমগুলাতে এই ধরনের recursion relation থাকে
if l is the left part and r is the right part of the interval then

dp[l][r] = min( dp[l][r] , d[l][m] + dp[m][r] ) + Inp[l][r] ;

এই প্রবলেমগুলাকে আমরা l থেকে r এ যে কোন mid point ধরে o( n ^ 3 ) এ যেখানে n হচ্ছে আমরা রডটাকে কতটা ভাগে ভাগ করতে পারি প্রবলেমটা সল্ভ করতে পারি , যা লিমিট একটু বড় হলে TLE দিবে । এই ধরনের প্রবলেম সল্যুশনে আমরা knuth's optimization technique use করতে পারি এতে code এর run time O ( n ^ 3 ) থেকে কমে এসে O ( n ^ 2 ) হয়ে যায় ।

তবে তা ব্যাবহার করা যাবে যদি নিচের দুইটা শর্ত বজায় থাকে ।

1.  quadrangle inequality
   Inp[ a ] [ c ] + Inp [ b ] [ d ] <= Inp[a][d] + Inp[ b ][ c ] where a <= b <= c <= d
2. monotonicity  

         Inp[b][c] <= Inp[a][d] where a <= b <= c <= d 

যদি সহজে বলি আমাদের পার্টিশন পয়েন্ট গুলা শর্ট হিসাবে থাকবে ( ছোট থেকে বড় )

আমরা একটা প্রবলেম নিয়ে এইটা কিভাবে এই ট্যাকনিক এ সল্ভ করা যাবে এইটা দেখি ।
Breaking Strings :

এই প্রবলেম এ একটা string কে কিভাবে break করলে সব থেকে মিনিমাম খরচে করা যাবে তা বলতে হবে । এইখানে string এর breaking point গুলা কি কি তা দেওয়া হয়েছে । এইখানে যে কোন পয়েন্ট এ ব্রেক করার সময় টোটাল কত lenght এর পার্ট থেকে এইটা ভাঙ্গছে এইটাই হচ্ছে এর cost ।

এর সমাধানে কোন পার্ট l - r এর জন্য এর mid[l][r] হচ্ছে এই পয়েন্ট যেখানে l - r  ভাঙলে সব থেকে কম হবে । যেহেতু middle point monotonously  end point এর উপর নির্ভর করে তাই
 mid[ l ][ r - 1] <= mid [ l ][ r ] <= mid [ l + 1 ][ r ] এইটা বজায় থাকবে । এইখানে আমরা l to r এর জন্য mid point update করতে থাকব mid[l][r-1] & min[l+1][r] এর পার্ট থেকে কারণ অবশ্যই best mid point ( partioning point ) হবে mid[l][r-1] <= our_target_partitioning_point <= mid[l+1][r ] for l - r interval .

প্রতিটা starting l এর জন্য আমরা চেক করে দেখছি যার জন্য m বার iteration লাগছে । run time  O( m ^ 2 ) .
প্রবলেম : 1
Reference Link : here