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

打開文本圖片集

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

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

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

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

1 引言

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