我有一个家庭作业问题，我试图解决好几个小时都没有成功，也许有人可以指导我正确思考它。
问题：
给定两个字符串 S1 和 S2，找到它们与间隙的最佳全局对齐的分数。差距成本由通用函数-() 给出。众所周知，对于间隙长度 - ≥ ， () 等于常数 C。
space O(min{|S1|,|S2|}*d)建议一种算法解决问题time O(|S1|*|S2|*d).
说明：在每个矩阵条目选择最佳间隙长度时，分别处理长度小于 d 的间隙和较长的间隙。除了常规最优值之外，在每个矩阵条目中存储通过使用较长间隙获得的最优值。
现在我们学习了以下两种算法：
与我们对成本函数一无所知的差距对齐：
与仿射间隙成本函数对齐
我的解决方案：
我知道我必须使用 d-rows 表才能满足空间要求，并使用这两种方法，但我很难将它组合成一个递归公式，这是我到目前为止所做的：
但是我不确定如何包括延长比 d 长的现有间隙的成本，甚至不确定如何检查我的递归公式是否正确。任何帮助，将不胜感激！