基于最大半环的DP问题函数式建模与验证

摘要： 针对在DP问题算法的设计和推导中缺乏对DP问题函数式建模算法与验证的细致研究，该文首先通过深入分析最大半环与DP类问题递推关系式的对应关系，找到满足最大半环性质的一类DP问题，使用最大半环对该类DP问题进行函数式建模；然后将实现的基于最大半环的函数式建模算法与Wimmer定义的递归函数结果进行等价性验证，从而保证了函数式建模算法的正确性；最后通过对lcs问题案例分析，验证了该方... （共8页）