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

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