如果某個問題符合動態規劃的主要條件，那麼就可以嘗試用動態規劃。一般地，動態規劃需要求解的問題具有 2 個核心特徵：
- optimal-substructure property：最優化的子結構屬性。
- overlapping subproblems：重疊的子問題集。
這的確有點難以理解，尤其是平時對算法不是很敏感的小夥伴。下面我舉一個例子，來解釋上面兩個特徵。
假如要求解某個最大連乘數組的最大值，發現子問題的最優解一定包括在原問題中，它是原問題的組成部分，並且，求以第 i + 1 個元素為索引的子數組一定要求出以第 i 個元素為索引的子數組的最大連乘。則這個問題可以用 DP 求解。
分享到:
閱讀更多 人工智能channel 的文章
