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. 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. -- M > > Why ? > I have heard this at some other places too. > Is this because it is a really broad category ? For example, a lot of graph > theory falls under same area. > > On an unrelated note, I like writing a recursive code and then simple > memoizing it. > Seems to me the best way to convert a tree to directed acyclic graph. > But cases like these are where we need table, where we need to save space. > Or probably we can save space using recursion too, I am not aware of it > though ? > > > -- > M > > > > > >
