1. You scan row by row from top to bottom.
2. At each row, you will either go down at the left end of the segment or at the right end.
3. You try both possibilities and get 2 sub-problems, which you solve recursively.
4. You keep a memoization table to avoid recursing too many times on the same sub-problems.
I did this iteratively:
Code: Select all
erased. works now