Problem 161
Posted: Tue Feb 12, 2008 11:36 am
Hello,
I'm not quite happy with my solution for p161, expecially after I saw how many brilliant dp solutions other people wrote in the forum. I'm always willing to learn something from people who write solution that are smarter than mine, so I was waiting for a forum post that I could be able to understand but it hasn't come. It seems that everybody has used a custom slightly different method and I'm not very confortable reading neither perl, nor complicated C code and so.
I tried reading and understanding C# and Java (and even C) solutions, but with no luck. Yarin's solution seems very nice, but I don't get it. I studied it and video printed a bunch of passes and I don't understand why it behaves like that. Also I don't know why he chose to set memo to -1 at first and then use the sum+1. I removed those +1 and -1 and it works fine. And also I discovered a couple of redundant checks within the if clauses, but at the end I still don't get how that solution works.
Same with Robert_Gerbicz's one, SmartSchizo's one, setosha's one, christer's ruby one, zeycus's one and Sternburg's one.
I read them all, a lot and a lot, but no lightbulb has come to me...
I was wandering if there is someone of you guys who would like to spend some time explaining me what is the best method to solve this problem. What I do not understand is why it is possible to solve it memoizing just 2 rows and not 3.
So... if anyone of you would like to help me just send me a pm here ok?
Thank you in advance,
sfabriz
I'm not quite happy with my solution for p161, expecially after I saw how many brilliant dp solutions other people wrote in the forum. I'm always willing to learn something from people who write solution that are smarter than mine, so I was waiting for a forum post that I could be able to understand but it hasn't come. It seems that everybody has used a custom slightly different method and I'm not very confortable reading neither perl, nor complicated C code and so.
I tried reading and understanding C# and Java (and even C) solutions, but with no luck. Yarin's solution seems very nice, but I don't get it. I studied it and video printed a bunch of passes and I don't understand why it behaves like that. Also I don't know why he chose to set memo to -1 at first and then use the sum+1. I removed those +1 and -1 and it works fine. And also I discovered a couple of redundant checks within the if clauses, but at the end I still don't get how that solution works.
Same with Robert_Gerbicz's one, SmartSchizo's one, setosha's one, christer's ruby one, zeycus's one and Sternburg's one.
I read them all, a lot and a lot, but no lightbulb has come to me...
I was wandering if there is someone of you guys who would like to spend some time explaining me what is the best method to solve this problem. What I do not understand is why it is possible to solve it memoizing just 2 rows and not 3.
So... if anyone of you would like to help me just send me a pm here ok?
Thank you in advance,
sfabriz