All Possible Cuts In All Possible Intervals For Choosing Last Operation
Get started
জয় শ্রী রাম
🕉Problems belonging to this category would have problem statement something like below or some variation of it:
Given a set of numbers find an optimal solution for a problem considering the current number
and the best you can get from the left and right sides.
Solution:
Make CUTS at all possible places (each CUT will create two INTERVALS on both sides, one on each side) and return the result for the CUT that gave the most optimal result. Now the biggest question is: what will each these CUTS represent ? Each of these CUTS will represent the last operation done in the interval that is getting divided by two by the CUT. And this will come naturally to you when you see all the examples we discuss in next several chapters. In Matrix Multiplication the first CUT will represent dividing the whole set of matrices into two sets and then multiplying those two set of matrices. So as you can understand, this multiplication will be the last multiplication done, because by that time both the two sets of matrices will already have their own multiplication ready. I know it does not make much sense now, so let's start looking at the examples.
Also, as we will see later while solving problems, FIGURING OUT WHAT THESE CUTS DEFINE IS THE MOST CHALLENGING PART OF SOLVING THIS KIND OF DP PROBLEMS. For some examples this might be very easy, like in Matrix Multiplication, but in many other cases it might take some serious critical thinking.
Template:
// from i to j
dp[i][j] = dp[i][k] + result[k] + dp[k+1][j]
Get the best from the left and right sides and add a solution for the current position.
for(int l = 1; l < n; l++) {
for(int i = 0; i < n-l; i++) {
int j = i+l;
for(int k = i; k < j; k++) {
dp[i][j] = max(dp[i][j], dp[i][k] + result[k] + dp[k+1][j]);
}
}
}
return dp[0][n-1]
One important thing to remember here, not all problems are optimization problems (like problems where we are concerned about find the total number of ways something can be achieved, like computing total number of unique binary tree configurations possible maintaning certain constraint(s) ). In this kind of problems, the solution would involve: for every interval, for every cut: compute the result and then add up all those results for that interval, as we see below. In these type of problems you won't have to worry about the concept of last operation.
// from i to j
dp[i][j] = dp[i][k] + result[k] + dp[k+1][j]
Get the best from the left and right sides and add a solution for the current position.
for(int l = 1; l < n; l++) {
for(int i = 0; i < n-l; i++) {
int j = i+l;
for(int k = i; k < j; k++) {
dp[i][j] += dp[i][k] + result[k] + dp[k+1][j];
}
}
}
return dp[0][n-1]
Let's look at some problems below to get a clear understanding of this kind of DP problems:
#1. Total Number of Unique Binary Search Trees
Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?Example:
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Java Solution:
Login to Access Content
Python Solution:
Login to Access Content
#2. Tree with Minimum Cost Leaf Nodes
Given an array arr[] of positive integers, consider all binary trees such that:
- Each node has either 0 or 2 children.
- The values of arr[] correspond to the values of each leaf in an in-order traversal of the tree. (Recall that a node is a leaf if and only if it has 0 children.)
- The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree respectively.
Example 1:
Input: arr = [6,2,4]
Output: 32
Explanation:
There are two possible trees. The first has non-leaf node sum 36, and the second has non-leaf node sum 32.
24 24
/ \ / \
12 4 6 8
/ \ / \
6 2 2 4
Solution:
This problem, on the surface, looks quite complex but once you have given enough thought and have applied the technique of "All Possible Cuts In All Possible Intervals For Choosing Last Operation", it becomes quite easy.
Let arr[] be the given array of nodes. These nodes are leaf nodes in inorder order. We would need to make a cut at every possible position in array arr[] where each interval would represent subtree with the nodes in that interval as the leaf nodes of the subtree. For each cut we compute the result and return the minimum result of all.
I have put my thought process and detailed logic of the algorithm in the inline comments in the code below:
Java Code:
Login to Access Content
Python Code:
Login to Access Content
Few characteristics of the DP problems like the above one:
-
This type of DP problems, at the heart, will always be like the above problem:
If you represent the problem as a tree then you will see that the tree will always have either 0 or 2 children, there will never be a node with just 1 child. So in general combination of root will have something non-null on left and on right. This kind of dp problem will also have n >=2. (while reading this, think of burst balloon problem). -
Now coming to the length: here we do not need to iterate the length from 1 to N,
Because since there will always be non null left and right subtree
length can never be equal to N.
for(int l = 1; l < n; l++) { for(int i = 0; i < n-l; i++) { int j = i+l; for(int k = i; k < j; k++) { dp[i][j] = max(dp[i][j], dp[i][k] + result[k] + dp[k+1][j]); } } }
-
I often get asked how to know when to use Dynamic Programming in a Tree problem ?
The answer is simple: if the problem is an Optimization Problem.
Of course, it also needs to show Optimal Substructure and Overlapping Subproblems properties to be able to use DP approach.
