Bottom-up dynamic programming (tabulation) differs from top-down memoisation in that
Atabulation uses no memory while memoisation needs O(n²)
Btabulation fills the table iteratively; memoisation is recursion plus a cache
Ctabulation only solves graph problems; memoisation only solves string problems
Dtabulation is exponential; memoisation is polynomial
Answer & Solution
Correct answer: B. tabulation fills the table iteratively; memoisation is recursion plus a cache
Both approaches reach the same answer in the same big-O, but they look different. Tabulation iterates over the table in dependency order with no recursion; memoisation keeps the natural recursion and adds a lookup cache. Tabulation tends to have smaller constants and no stack-depth worry; memoisation is sometimes easier to write.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for