So, what is Mixt Dynamic Programming?
First of all, what is Dynamic Programming? The process in which we break a big problem into smaller ones, solve those, then combine them together to get the answer for the original one. Coooool!
Mixt Dynamic Programming is the version in which the big problem is a range and the smaller ones are subsequences of that range. So, the dp looks like this dp[Left][Right] = the answer for subsequence [Left…Right]. Coooool!
What about the recurrence relation? Most the time you will need an intermediate point. Let’s call it p, it’s significance depends on the problem. You are going to fix this p with a for loop and construct the recurrence relation based on it.
Real life example?
I got one, and it is pretty challenging. Check this Leetcode Interview Question out, explained and coded: Burst Balloons