# Find optimal alignment between 2 strings with gap cost function

I have a homework question that I trying to solve for many hours without success, maybe someone can guide me to the right way of thinking about it.

The problem:

Given two strings S1 and S2, find the score of their optimal global alignment with gaps. The gap costs are given by a general function-๐ค(๐). It is known that for gaps lengths-๐ โฅ ๐, ๐ค(๐) equals a constant C.

Suggest an algorithm solving the problem with space O(min{|S1|,|S2|}*d) and time O(|S1|*|S2|*d).

Instruction: When choosing the optimal gap length at each matrix entry, process separately the gaps of a length less than d and the longer gaps. Store in each matrix entry the optimal value obtained by using the longer gaps, in addition to the regular optimal value.

Now we learned the following 2 algorithms:

Alignment with gaps where we do not know anything about the cost function:

Alignment with affine gap cost function

my solution:

I know that I have to use a d-rows table in order to meet the space requirements, and to use both methods but I'm having troubles to combine it into one recursive formula, Here is what I have done so far:

But I'm not sure how to include the cost for elongating an existing gap that is longer than d, and not even sure how to check if my recursive formula is correct. Any help would be appreciated!