The Ultimate Mixt Dynamic Programming Tutorial You Will Read

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

Keep hustling,

Andy(Romeo)

6 Likes

I am a true-lover of Mixt Dynamic-Programming.

Related problems:-

1)Google Kickstart:- https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050edc/000000000018666c

2)Codechef:- i)https://www.codechef.com/problems/CIRMERGE ii)https://www.codechef.com/ICOP1904/problems/GRP

3)Hackerearth:- https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/sonya-clears-the-array-icpc-2/description/(Legendary-Problem)

3 Likes

Really nice!!
I’m pretty impressed with your channel Andy!
Hope you keep at it for the 60 days haha so we get a lot to learn :slight_smile:

3 Likes

Thanks brother! I will, I learn as much as you do by each video!

2 Likes

@chiriacandrei2 Love your channel bro, can you do some more mixt-dp problems? I would love to see them. How to send you a problem which you might like to solve ?

1 Like