Another cool Python DP hack is using @functools.lru_cache to perform the memoization (beware of the maxsize parameter though).