[Think DP] How I approach DP problems (Guide for Beginners)
Let's take this problem 1043. Partition Array for Maximum Sum
Here problem is to find the maximum sum from atmost k partition subarrays where each partition subarray contains max element/value of subarray for all its columns.
Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: Array will be [15,15,15,9,10,10,10]
Here 0-2 is taken as one subarray and its max is 15 then all its column values is 15
--> sum = 45
Then 3-3 is taken as one subarray and its max is 9 then all its column values is 9
--> sum = 9
Then 4-6 is taken as one subarray and its max is 10 then all its column values is 10
--> sum = 30
Total sum = 45+9+30 = 84
Step 1 : -First thing is to understand the prblm, what it is asking.
Step 2:- Identify the variables which you will need and try to formulate the recursive approach.
``
Pseudo code
// [ ] -> given array
// i -> starting index from which partition will be done
// k -> partition variable
// n -> size of array
if(i == n-1) return [n-1];
// base condition for this consider smallest input and try to find its ans
[],i,k
int sum = 0;
int max = -1;
for(int j=i;j<i+k && j<n;j++){//loop will run upto j<n or j<partition limit (i+k)
max = max(max,[j]);// max element in the subarray
int res = ([],j+1,k) //assume you have its sub prbm ans and just call for it
//find ans for current probm at i
//here we need to fill subarray with the max value --> (j-i+1)->gets subarray len
//max*(j-i+1) --> gets partition subarray sum
sum = max(sum, max*(j-i+1) + res);
//ans will be the current sum + sub prbm result (res).
}
return sum;
``
Step 3 :- If you can think of above formulation then you can easily write memoized solution and state of DP will the of number of changing variables.
Like in above solution only i is changing --> dp[n] will be used
Step 4 :- Main and tough thing beginners like me find, Is to write Bottom Up solution for above solution.
Here is the trick😎
From the above formulation ,
---> now check how the variables are changing
---> fill the dp table in that fashion
---> Fun part whole solution will be same just note the above 2 points
``
int res = ([],j+1,k)// see this
//Here j+1 call is made which means during filling of table
// first fill the cells greater than j then you will able to use dp[j+1]
``👉 Final Solution🔥
``
public int maxSumAfterPartitioning(int[] arr, int k) {
/*
if(i == n-1) return [n-1];
[],i,k
int sum = 0;
int max = -1;
for(int j=i;j<i+k && j<n;j++){
max = max(max,[j]);
int res = ([],j+1,k)
sum = max(sum, max*(j-i+1) + res);
}
return sum;
**/
int n = arr.length;
int []dp = new int[n];
dp[n-1] = arr[n-1];//fill the base case
//loop from behind because in above we need ans of j+1
// It can be done from front but I like this way its more intutive to me.
for(int i=n-2;i>=0;i--){
int max = -1;
int sum = 0;
for(int j=i;j<i+k && j<n;j++){
max = Math.max(max,arr[j]);
int sub = j<n-1?dp[j+1]:0;//get sub problem solution
sum = Math.max(sum,max*(j-i+1)+ sub);//make current problem solution
}
dp[i] = sum;//fill current state
}
return dp[0];
}``
If you find my post helpful🌟, Please do comment and Upvote!
Thank You. 🤞