On Wed, Jan 15, 2014 at 10:13 PM, Matthias BUSSONNIER < [email protected]> wrote:
> > Le 14 janv. 2014 à 21:45, Shashwat Anand a écrit : > > > > Assuming you have computed row P from 1 to Q (included) , you don't > need the values > > of row P-1 from 1 to Q (excluded) anymore. So you can use a circular > buffer. > > So you store Q+N-(Q-1) = N+1 values. > > > > > > Awesome ! > > I never thought, we can use circular buffer like this. Quite nifty an > approach it is. > > > > Why is it slow then ? Is it due to % operator ? > > Yes, probably I suppose, you can probably avoid the % operator at each > loop though > as you know in advance that you will get back to 0 index every N+1. > Haven't tried too much though. > > > > > See https://en.wikipedia.org/wiki/Longest_common_subsequence_problem > > Reduce the required space section (they don't explain why exactly but > once you > > see the matrix you'll get it) > > > > > > This one is textbook, use 2 rows and keep on alternating between them. > > A lot of problems like Longest Common Subsequence, Shortest Common > Supersequence etc are > > solved via this. Also this technique is fairly common in programming > competitions. > > Well, you apparently did CS classes, I never did, but get to the same > conclusion :-) > > > > > > I also found that "Dynamic Programing" is an over-used term. > > Crappy internet so can't even search on SO and wikipedia, but IIRC > Dynamic Programming means that you solve a problem by solving smaller > problem. > I have just too often come in contact with response to question like, > "this require Dynamic Programming and it is a highly advance technics > that only senior programmers can handle" for problem as simple that > Fibonacci sequence. > > Those sub problems needs to be overlapping though. When you solve a large problem by solving smaller problems, you are doing divide and conquer. Say merge sort. But if those problems are overlapping, you can convert recursion tree into a dag. Here it a rather fun game theory problem if you want to solve, source [1] There are 2 players A and B. N pots of gold are arranged in a line, each containing some gold coins (the player can see how many gold coins are there in each gold pot - perfect information). They get alternating turns in which the player can pick a pot from one of the ends of the line. The winner is the player which has highest number of gold coins at the end. The objective is to maximize the number of gold coins collected by A, assuming B also plays optimally. A starts the game. > BTW, have anybody ever seen a recursion using Fib, that at the end > explicitly state that > we can get the nth term without closed form expression. > You probably would want to read this. [2] [1] https://www.quora.com/Dynamic-Programming/How-do-you-solve-the-pots-of-gold-game [2] http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/05-dynprog.pdf
