Also like O(N^2) is surprisingly doable even for very big N. Maybe I shouldn't have been surprised, but another problem was N^2 for a pretty big N (100k) with a dynamic programming. I was worried it would never finish

But making a 100k by 100k matrix in julia really isn't so bad (and can use memoization), just rent a big machine on GCP for an hour or two, and it chewed through it fast