h******3
发帖数: 351 | 1 1373 blogged the question "unique paths" using backtracking recursion, top
down memoization, bottom-up dynamic programming.
There is also a follow up question: enumerate all possible paths.
For example, n = m = 2, all possible paths = 6, which are
(2,2)->(1,2)->(0,2)->(0,1)->(0,0)
(2,2)->(1,2)->(1,1)->(0,1)->(0,0)
(2,2)->(1,2)->(1,1)->(1,0)->(0,0)
(2,2)->(2,1)->(2,0)->(1,0)->(0,0)
(2,2)->(2,1)->(1,1)->(1,0)->(0,0)
(2,2)->(2,1)->(1,1)->(0,1)->(0,0)
is this a NP-Complete problem? | s**x
发帖数: 405 | 2 This is exponential time, but not NP-complete. | h******3
发帖数: 351 | 3 I think it is hard to record paths if implemented using dp or memoization,
looks like backtracking is the best way to enumerate. Maybe I can persist
each nodes on the recursion tree. And enumerate all the root to leaf paths
using some algorithm.
【在 s**x 的大作中提到】
: This is exponential time, but not NP-complete.
|
|
