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

打開文本圖片集

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

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

中圖分類號：G642        文獻標識碼：A

文章編號：1009-3044（2022）24-0069-03

1 引言

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