动态规划 动态规划英語Dynamic programming简称DP是一种在数学管理科学计算机科学经济学和生物信息学中使用的通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法 动态规划常常适用于有重叠子问题和最优子结构英语Optimal substructure性质的问题动态规划方法所耗时间往往远少于朴素解法 动态规划背后的基本思想非常简单大致上若要解一个给定问题我们需要解其不同部分即子问题再根据子问题的解以得出原问题的解 通常许多子问题非常相似为此动态规划法试图仅仅解决每个子问题一次从而减少计算量一旦某个给定子问题的解已经算出则将其记忆化存储以便下次需要同一个子问题解之时直接查表这种做法在重复子问题的数目关于输入的规模呈指數增長时特别有用