Dynamic Programming ​

The core of dynamic programming is to identify sub-problems within the larger problem, and resolve the larger problem using information about solutions to previous sub-problems.

1. Visualize examples
   • A model that shows up all the time is the Directed Acyclic Graph ![[../../../media/algo-dynamic-programminer-nodes.png]]
   • Finding subsequences is the same as finding paths in a graph
   • Example: Minimum cost to get up stairs problem: The solution was to understand that the cost to reach step $n$ is minimum_cost($n-i$) + cost ($n-i$), where $i$ is the number of steps allowed (e.g. 2, see LeetCode problem 756?)
2. Find an appropirate subproblem
3. Find relationships between subproblems
4. Generalize the relationship

Often the hardest part of solving a dynamic programming problem is organizing the information in the correct way to find a reasonable way to solve the larger problem via sub-problems

A solution to a dynamic programming problem depends on two fundamental components: solving sub-problems to a larger problem that will eventually resolve themselves into the solution to the larger problem, and caching to ensure that redundant operations are limited.

• Dynamic programming is typically used when the interviewer is asking a hard problem.
• Solutions are either recursive or iterative, though the recursive solutions are typically more intuitive, iterative ones are often more efficient in terms of space and time complexity.

16.1 ​

tough, failed, review

16.2 ​

tough, failed, review

16.3 Count the numer of ways to traverse a 2d array ​

Perfect! Not even one error.

• The key insight was that each square is the sum of squares above and to it's left. This is a crucial aspect of DP, namely, identifying the solution to the subproblem, and the nature of the subproblem itself.
  • Recognize that it all comes down to the initial state how can the initial point of state be adjusted to, somehow, arive at the final state.
• Used a 2d array to cache the the current state of alternative traverses.
• Used an iterative solution.
• Authors used a recursive approach instead

16.6 Knapsack problem ​

Fundamentally, I failed to see the core sub problem that needed to be solved... The trick is to use recursion to take the max of the current bag with a given item and without it. In this way, you have to start with th furthest right elements and slowly remove them

Lessons Learned ​

• Once you have found a way to solve the problem, implementing it is an issue too. Consider using a 2D array (or table) to encode the results of the sub problem.

LC 70 Climbing Stairs ​

This is a dynamic programming problem. You can brute force a solution using a Fibonacci style recursion, but you will run into a timeout exception.

Solution 1: Memoization. This approach leverages a cache (or memo) to store values that have already been computed, effectively turning the $O(2^n)$ time recursive solution into an O(n) solution since you can use constant lookups when computing values you've already seen.

class Solution:
    def __init__(self):
        self.memo = {}

    def climbStairs(self, n: int) -> int:
        '''
        Time complexity, O(n) because of memoization
        Space complexity, O(n) is implicitly allocated on the call stack
        '''
        self.memo[0] = 1
        self.memo[1] = 1
        return self.helper(n)

    def helper(self, n):
        if n in self.memo:
            return self.memo[n]
        else:
            self.memo[n] = self.helper(n-1) + self.helper(n-2)
        return self.memo[n]

class Solution:
    def __init__(self):
        self.memo = {}

    def climbStairs(self, n: int) -> int:
        '''
        Time complexity, O(n) because of memoization
        Space complexity, O(n) is implicitly allocated on the call stack
        '''
        self.memo[0] = 1
        self.memo[1] = 1
        return self.helper(n)

    def helper(self, n):
        if n in self.memo:
            return self.memo[n]
        else:
            self.memo[n] = self.helper(n-1) + self.helper(n-2)
        return self.memo[n]

Solution 2: Iteration. This approach doesn't run into a timeout error, because you're accumulating the running total as you conduct the iteration. For this solution, create variables curr, prev = 1, 1 and then run a for loop to accumulate a next = curr + prev value. Take care to catch conditions when n is 0 or 1, and to get the number of iterations correct to account for a starting offset.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0 or n == 1:
            return 1
        
        prev, curr = 1, 1
        for i in range(2, n+1):
            next = curr + prev
            prev = curr
            curr = next
        return next

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0 or n == 1:
            return 1
        
        prev, curr = 1, 1
        for i in range(2, n+1):
            next = curr + prev
            prev = curr
            curr = next
        return next

Resources ​

• Mastering recursive programming