[Reincarnate]

I mean right now I'm using a memoization class which is the "lazy man's" way to use dynamic programming in Python (and in this case it's memoizing a lot more than it needs to, but I digress -- this was just to ensure the score's right and recursion is easy to code).

Basically, at each step of the DP, it takes the max of three possibilities:

1. Inserting a gap in the second sequence, incurring the g-cost, and then continuing onward
2. Inserting a gap in the first sequence, incurring the g-cost, and then continuing onward
3. Not inserting a gap, so taking the score of the base-pair, and continuing onward

If we run out of bases in a particular string, then we just incur gap-costs for the rest (however long the remaining string is)

Since it's constantly taking the max of all three possibilities at each step, and recursing at each step, you get the maximum possible score from all possible ways of inserting gaps/not inserting gaps every which way.

For really long strings, this could take forever, but that's what DP is for:

Memoization (in this case) is just caching results at intermediate steps so they don't have to get re-calculated over and over again (which is the heart of DP).

For instance, if I asked you to add 1+2+3+4+5, you'd tell me "15!"
Now if I asked, "Okay, now what is 1+2+3+4+5+10", you'd very quickly tell me "25!"

In this case, you knew it was just 10+your previous answer, so you didn't re-calculate "1+2+3+4+5+10" from scratch. Memoization is basically the same thing.

Disclaimer: not a CS expert, so I'm sure someone will come along and point out all the flaws in what I've said