Timeline for Proving optimality of a dynamic programming algorithm
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot | replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/ | |
| Sep 23, 2014 at 16:43 | comment | added | D.W.♦ | @Cris, As Yuval says, part (3) is the most essential part. But that doesn't mean you can neglect the rest. You should still write down the recurrence carefully. It's a prerequisite to having a proof. It might be the easy part; if so, do it, then go focus on the hard part. But leaving it out of your question makes it impossible for us to give you feedback on that part, and might cause you to head in an entirely wrong direction (if you're not able to formulate the recurrence properly). | |
| Sep 23, 2014 at 13:24 | comment | added | Yuval Filmus | @Cris The heart of the problem is part (3). Make a stab at proving (or refuting) it yourself. It may be "non-trivial", as you mention, but that just means that you have to think a bit. | |
| Sep 23, 2014 at 10:11 | comment | added | Cris | I do have an algorithm, as well as I have it implemented. Just looking at the recurrence does no help, because it's being correct solely depends on the assumption I made. Things you gave me are vague ideas, what would actually help is some starting point for this specific problem, such as "let's take some optimal sequence of moves on string $s$, WLOG we can assume that the last move is... / there exists a position such that..." etc. | |
| Sep 22, 2014 at 23:34 | history | answered | D.W.♦ | CC BY-SA 3.0 |