Loading
Loading
Solve each overlapping subproblem once and remember the answer.
When a problem decomposes into subproblems that recur, compute each one once and store it. The two ingredients are optimal substructure — the answer is built from answers to smaller instances — and overlapping subproblems, which is what makes memoising worthwhile. Without the overlap, plain recursion is already fine.
Name the state first. Write down exactly what `dp[i][j]` means as an English sentence before writing any code. Almost every dynamic programming bug is a state whose meaning drifted halfway through the implementation.
The shape, not a solution. Adapt the condition and the state to the problem in front of you.
def top_down(n): """Memoised recursion: closest to how you reason about the problem.""" memo = {} def solve(state): if state in memo: return memo[state] if is_base_case(state): return base_value(state) best = min(solve(nxt) + cost(state, nxt) for nxt in choices(state)) memo[state] = best return best return solve(n) def bottom_up(nums): """ Tabulation. dp[i] = the best answer considering the first i elements. Writing that sentence down before the loop is the whole discipline. """ dp = [0] * (len(nums) + 1) dp[0] = base_value() for i in range(1, len(nums) + 1): dp[i] = combine(dp[i - 1], nums[i - 1]) return dp[len(nums)] def rolling_array(nums): """When dp[i] depends only on dp[i-1], two variables replace the table.""" previous, current = 0, 0 for value in nums: previous, current = current, combine(previous, current, value) return currentSign in to keep a note here. It is free, and nobody else can see it.
Sign in