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 .

	const int NX = 1005 ;
	const Long INF = 1e17 ;
	Long dp[NX][NX] , mid[NX][NX] , inp[NX] ;
	int n , m ;
	Long kunth_optimization()
	{
	ms( dp , 0 );
	ms( mid , 0 );
	int l , r , s ;
	for ( s = 0 ; s <= m ; s++ ) // length of the substring
	{
	for ( l = 0 ; l + s <= m ; l++ ) // left starting part
	{
	r = s + l ; // right ending part
	if( s < 2 )
	{
	dp[l][r] = 0 ; // base case , nothing to break
	mid[l][r] = l ; // mid is equal to left border
	continue ;
	}
	int mleft = mid[l][r-1]; // knuth's tricks
	int mright = mid[l+1][r];
	dp[l][r] = INF ;
	for ( int mm = mleft ; mm <= mright ; mm++ )
	{
	Long tmp = dp[l][mm] + dp[mm][r] + ( inp[r] - inp[l] );
	if( tmp < dp[l][r] )
	{
	dp[l][r] = tmp ;
	mid[l][r] = mm ; // updating mid
	}
	}
	}
	}
	return dp[0][m] ;
	}
	int main()
	{
	// I will always use scanf and printf
	// May be i won't be a good programmer but i will be a good human being
	//cout << ( 1 << 30 ) << endl ;
	while( scanf("%d %d",&n,&m) == 2 )
	{
	m++ ;
	inp[0] = 0 ;
	for ( int i = 1 ; i < m ; i++ ) inp[i] = LL ;
	inp[ m ] = n ;
	printf("%lld\n",kunth_optimization());
	}
	return 0;
	}

view raw knuth.cpp hosted with ❤ by GitHub

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