基于最大半環(huán)的DP問題函數(shù)式建模與驗(yàn)證

摘要： 針對在DP問題算法的設(shè)計(jì)和推導(dǎo)中缺乏對DP問題函數(shù)式建模算法與驗(yàn)證的細(xì)致研究，該文首先通過深入分析最大半環(huán)與DP類問題遞推關(guān)系式的對應(yīng)關(guān)系，找到滿足最大半環(huán)性質(zhì)的一類DP問題，使用最大半環(huán)對該類DP問題進(jìn)行函數(shù)式建模；然后將實(shí)現(xiàn)的基于最大半環(huán)的函數(shù)式建模算法與Wimmer定義的遞歸函數(shù)結(jié)果進(jìn)行等價(jià)性驗(yàn)證，從而保證了函數(shù)式建模算法的正確性；最后通過對lcs問題案例分析，驗(yàn)證了該方...