I enjoyed this post, thank you! For the benefit of anyone else reading, some context that I felt would have helped: The toy problem being considered is the foll

I enjoyed this post, thank you! For the benefit of anyone else reading, some context that I felt would have helped: The toy problem being considered is the following. You are given a sequence of historical prices (of a single stock or index or whatever), one for each day: day 1 2 3 ... n price p1 p2 p3 ... pn The task is to annotate each day i with a (retroactive) decision z_i ∈ {buy, sell, do nothing}, and do this optimally, subject to the constraint that you cannot sell before you buy, cannot "buy" twice without an intervening "sell" and vice-versa, etc. And there are indeed dynamic-programming algorithms to solve this quickly, which you can find on Leetcode writeups and whatnot. (Whether or not this has any resemblance to real-world trading is not the point of the toy problem, which is about computational techniques. See e.g. Knuth's article “Are toy problems useful?” from Chapter 10 of https://cs.stanford.edu/~knuth/cs.html https://cs.stanford.edu/~knuth/cs.html, or “Puzzles versus the real world” on pages 7–9 of TAOCP Vol 4A.) Another way to model it is with two-valued y_i ∈ {do nothing, "change state"}, where "change state" means buy if you haven't bought and sell if you have, with the last day's decision forced (you have to end in the sold state), which shows why there are 2^{n-1} possibilities to optimize over. But there's yet another way of modeling the problem, presented in this post, where we have 2n-2 boolean variables x1, x2, x3, x4, … denoting respectively the choices of whether or not to "buy on day 1", "sell on day 2", "buy on day 2", "sell on day 3", and so on, and now the problem becomes one of the form: maximize w1x1 + w2x2 + w3x3 + … such that f(x1, x2, x3, ...) = 1 where f is a boolean function denoting whether the 0-1 values assigned to the x_i variables is "valid" (does not have both buy and sell on the same date, has a buy before a sell, etc). Now, this may seem hard to optimize over, but BDDs (binary decision diagrams) are a data structure that can represent such functions compactly, and in this case (because of the problem structure) the entire truth table (over all possible 2^{2n-2} assignments to xi, with 2^{n-1} "true" values among them) can be represented as a BDD with 2.5n nodes, and with a standard algorithm can be optimized over. This gives an algorithm that is just as fast as the dynamic programming algorithm (almost? asymptotically?), and is a fun exercise to play with BDDs, which this post describes very well.