In DP, how is divide and conquer different from knuth optimisation

1

Here is what I understand:

I understood how divide and conquer works here. If DP(x) = Space[y] and DP(x+dx) = Space[y+dy] (where dy and dx are either both positive or negative) - we can use this fact to our advantage.

For example if F(2) is 4 and if F(4) is 10, and I am told that F(3) can only be between 4 and 10, I dont need to waste time searching for answer in spaces 1,2,3 or 10,11,12 etc. So I divide my search space and conquer the problem.

(Sorry for the long preface)

Okay, so how is this different from Knuth’s optimisation?
Yes, I went through this: Dynamic Programming Optimizations - Codeforces

@vijju123 @lebron

2

IMO they are not different. knuth optimisation is just a clever way to reduce your search space.

1 Like
3

Thank you. Any link that explains Knuth optimisation properly?

4

It is little hard to follow but covers everything from scracth
Link

2 Likes
5

Awesome! I will go thru it and come back with questions!
@gagan86nagpal - Thanks, friend!