Category Archives: Dynamic Programming

Dynamic Programming, Interview Questions

Longest Increasing Subsequence (Leetcode Dynamic Programming Study Plan)

This is a truly classic problem. The opener in one of the big algorithms textbooks on dynamic programming, I’m glad it’s included in the dynamic programming study plan. I bet there is an even prettier way of writing this code, but here is the solution I have:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) == 0: return 0
        T = [1] # the first thing is always a sequence
        for i in range(1, len(nums)):
            best = 1
            for j in range(i):
                if nums[j] < nums[i]:
                    best = max(best, T[j]+1)
            T.append(best)
        return max(T)

Recurrence

T[i] is the length of the longest increasing subsequence that has to include the i’th element in nums. Compare to the recurrence in the previous question we discussed; there are similarities, but the big difference here is that our solution at i can build off of any previous solution that ends with a value smaller than ours, versus our solution having to be just contiguous with the previous solution.

So in more depth:

  1. T[i] is the length of the longest increasing subsequence of nums[:i+1] that include nums[i]. Taking the max of this array will find the solution.
  2. T[i] is computed via that append call, so we append the best value. We consider all values in T[:i] — recall T[j] is the length of the longest subsequence ending with nums[j]. If nums[j] < nums[i], we can “continue” that subsequence with nums[i], and so increase its length by 1.
  3. Through the “magic of recursion”, we are able to kick-start this process by defining T up to T[:1], i.e., T = [1].

The Dasgupta algorithm book explains this in a very graph-theoretic way, which I appreciate but is also kind of a lot.

See here for more dynamic programming problems and solution.

Dynamic Programming, Interview Questions

Maximum Subarray (Leetcode Dynamic Programming Study Plan)

1 Comment

How much of this question is carefuly application of arithmetic laws? Computing the maximum subarray seems like a simpler form of the classic longest increasing subsequence, but with fewer edges in the graph and a more “monotonic” (?) recurrence.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        T = [nums[0]]
        for i in range(1, len(nums)):
            T.append(max(nums[i], nums[i]+T[i-1]))
        return max(T)

Recurrence

The recurrence, such that it is, is that T[i] is the maximum sum of the array nums[:i+1] (to use slice syntax) that must use i. As in other questions, we’re embedding a decision in our recurrence. That would explain how the final max(T) works.

The big question is how does the for loop maintain the recurrence? How do we know that T was computed correctly? I don’t have a formal write-up, but to me the intuition follows from:

  1. If any prefix is >0, then it’s worth including that prefix.
  2. If any prefix is <= 0, then it’s not worth including it.

Distinct from the classic problem of longest-increasing-subsequence, we are only allowed to make limited choices, here: we can either attach ourselves to an existing sub-array, or start a new sub-array. If the existing sub-array has a positive influence (turn of phrase), then we might as well jump aboard. The choices are “simple”, in that sense.

This is included with all the other dynamic programming questions listed here.

Bit Manipulation, Dynamic Programming, Interview Questions

Counting Bits (Leetcode)

Another from the archives! I had a lot of fun with this one. Would others? I don’t know! We can use a sort-of dynamic programming approach (maybe this is a good replacement for that frustrating “Fib” standard warmup?) to avoid calling popcount over and over again. Not sure what’s actually faster on hardware, but I like the principle here.

This is a good algorithmic-thinking question, I think. Requires some fluency with bit manipulation, though.

class Solution {
public:
    vector<int> countBits(int num) {
        if (num == 0) { return {0}; }
        if (num == 1) { return {0, 1}; }
        if (num == 2) { return {0, 1, 1}; }
        vector<int> res(num+1);
        res[0] = 0;
        res[1] = 1;
        for (int i = 2; i <= num; ++i) {
            const int lastBit = i % 2;
            res[i] = res[i/2] + lastBit;
        }
        return res;
    }
};

Notes

Additional implementation details? I don’t know. I found it reassuring that the length of the output is required to be num, because there’s always that potential psuedopolynomial trap. Fixing the output size (versus, say, we’d have to return the total numbers of 1s or something) helps make it unambiguous that we’d at least be able to iterate through all inputs.

Other bit-manipulating questions are collected here. Other dynamic-programming questions are collected here.

Dynamic Programming, Interview Questions

House Robber (Leetcode Dynamic Programming Study Plan)

This was a nice dynamic programming exercise, and part of the Leetcode-defined study guide. This is a fun alternative to the Dasgupta et. al. intro question of longest increasing subsequence. It feels like the same flavor. Perhaps a more peaceful formulation would be making it like choosing a sequence of moves in some game show, to win money.

The Core Approach

This is the first question in the sequence that really motivates, to my mind, a “real” dynamic programming formulation. In this case, we want a table T such that T[i] is the “best” thing for some category. To me the most interesting complication is how to express that choice implicitly in T. The counterintuitive trick I’ve learned is to have T involve committing to that choice.

Just as the Dasgupta LIS example has T[i] be the longest increasing subsequence ending at that point (so it’s committed to using the ith element as part of the sequence), we should have T[i] in this question be the most money you get if the last house you rob is house i.

On a more mechanical level, there are two harsh jumps in my mind:

  1. We’re going from a linear algorithm to a quadratic algorithm. Not a problem, but as people seem to approach dynamic programming with some fearful awe, it may be worth to clear the way and say multiple scans over the table is OK.
  2. The solution to the problem is not (necessarily) the last cell of the table. That is again fine, but again different from the previous questions.

The solution

No further ado, complete with unaltered comments to myself.

class Solution:
    def rob(self, nums: List[int]) -> int:
        T = []
        # T[i] = most money when comitting to robbing house at i
        # Observation: we encode the decision into our definition
        # of T, that's how we avoid having to think about more than
        # 1 house at a time (we instead look at the previous... 3 options?)
        # Interesting inputs: [10, 1, 1, 10], you don't want to rob either "1" house
        for i, v in enumerate(nums):
            options = T[:i-1] + [0]
            T.append(max(options)+nums[i])
        return max(T)
Dynamic Programming, Interview Questions

Min Cost Climbing Stairs (Leetcode Dynamic Programming Study Guide)

And we’re back with our study plan. The next question follows from the previous pretty naturally, now we want to find a particular path, one that is optimal in some sense. In this case, it’s the min-cost path.

So I’m coming around to the approach presented in this study plan. There is a design behind it; my concern is that the design is a bit opaque to the new student. I can see it as someone familiar with the topic and knowing what ideas to build up to. In this question:

  1. We make the jump (finally) to an optimization problem. We want to compute the -est if something (in the case, the small-est).
  2. The syntax of the solution will present a lot of the common patterns to look for: you have a recurrence that basically feeds off of previous elements from the table you’re building, as well as a component of the input.

Wishlist

There are some rough edges to this question. Again, I’m coming around to this approach, but if I could ask for some things:

  1. The question itself is a bit ambiguous. The effect is that the best answer is either ending on the last, or the second-to-last step. I wonder how the question would look if you always had a cost-0 step at the end. You’d end up in the same place, and I think it’d help remove ambiguity about where the path actually has to end.
  2. Similar thing with the beginning, though to a lesser extent.
  3. My approach, and maybe due to my own limitation, ended up with slightly different offsets from i in my new table (minCost) and the input table (cost). If/when I teach this, I’d want to make sure those indices line up in the material I present.

With that final caveat, here’s my quick solution.

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # trusting the invariants than len(cost) > 1
        minCost = [0, cost[0], cost[1]]
        # mincost[i-1] is the min-cost of landing on that step
        for i in range(2, len(cost)):
            minCost.append(min(minCost[-1], minCost[-2])+cost[i])
        # we essentially can either end on the last, or second-to-last, step
        return min(minCost[-1], minCost[-2])

I’m trying to collect all the study-plan questions under this tag. All dynamic programming questions go under this other tag.

Dynamic Programming, Interview Questions

Tribonacci (Leetcode Dynamic Programming Study Plan)

We meet again. Our second question in the study plan is the question on how to compute the n-th tribonacci (a pun off of “fibonacci”) number. Again I am not sure if we should really use this to teach dynamic programming! We’re just practicing the array tables.

In truth I don’t have much to say. This definitely is able to be done after solving the first question. I am a fan of these sort of “very basic extensions” to previous questions to help the student drive home the idea. I just went with the table approach this time.

I suppose it’s interesting that the question is articulated slightly differently in the codewars question. There is something a bit more general there; I prefer the specificity if I were using this question in a classroom or review setting. Maybe as a side-note, or a “quick” homework question, would be to further extend to these sort of signatures.

Anyways, here’s the solution:

class Solution:
    def tribonacci(self, n: int) -> int:
        a = [0, 1, 1]
        if n < 3: return a[n]
        for i in range(3, n+1):
            a.append(a[i-3]+a[i-2]+a[i-1])
        return a[-1]
Dynamic Programming, Interview Questions

Fibonacci (Leetcode Dynamic Programming Study Plan)

I’m changing up the format. I’m going to be going through a so-called “Leetcode Study Plan”, in particular the one on dynamic programming, and see how it compares to what I’d do for teaching this topic. I will “just” be solving the problems as with my other posts here, but I’ll hopefully be finding good notes to fulfill a larger write-up of how one might, or might not, use this to help their students.

Findings

To be honest, I don’t think this is off to a great start with Fibonacci. I suppose it’s nice to use arrays to compute intermediate values, but the recurrence here is meaningfully simpler than what comes up in “real” (or at least the hard) dynamic programming problems. In particular, we don’t choose from a collection of solved subproblems, we always know we’ll use the n-1 and n-2 solutions to create the n solution.

Speaking of solutions… I playfully made one without any arrays. Presumably if I had to use this to teach dynamic programming, I would use the “array based” method even though it’s not needed, as demonstrated:

class Solution:
    def fib(self, n: int) -> int:
        if n == 0: return 0
        if n == 1: return 1
        prevprev = 0
        prev = 1
        for i in range(2, n+1):
            tmp = prev + prevprev
            prevprev = prev
            prev = tmp
        return prev

So if I want to play along more, we have:

class Solution:
    def fib(self, n: int) -> int:
        if n == 0: return 0
        if n == 1: return 1
        a = [0, 1]
        for i in range(2, n+1):
            a.append(a[i-1]+a[i-2])
        return a[-1]

I will admit it looks prettier.

This and more dynamic programming problems will be listed here.