動(dòng)態(tài)規(guī)劃法的教學(xué)引例——數(shù)字三角形問題

打開文本圖片集

摘要：針對數(shù)字三角形問題，設(shè)計(jì)了深度優(yōu)先搜索算法，記憶化搜索算法，動(dòng)態(tài)規(guī)劃法的不同解決方案。文章從算法思想、算法實(shí)現(xiàn)以及算法復(fù)雜度三個(gè)部分對該問題的教學(xué)方法進(jìn)行了探討，便于學(xué)生理解和掌握遞歸和動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想。

關(guān)鍵詞：數(shù)字三角形;深度優(yōu)先搜索算法;記憶化搜索算法;動(dòng)態(tài)規(guī)劃法

中圖分類號(hào)：G642        文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）24-0069-03

1 引言

動(dòng)態(tài)規(guī)劃[1]（Dynamic Programming 簡稱DP） 是解決“多階段決策問題”的一種高效算法。（剩余5552字）