第十章动态规划

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。

概念引入

动态规划（Dynamic Programming, DP）是一种算法设计方法，广泛用于求解各种优化问题。其核心思想是将一个复杂的问题分解成若干个子问题求解，同时将子问题的解存储起来以避免重复计算。动态规划的基本特点和步骤包括：

Originally Answered: How should I explain what dynamic programming is to a 4-year-old?

*writes down “1+1+1+1+1+1+1+1 =” on a sheet of paper*
“What’s that equal to?”
*counting* “Eight!”
*writes down another “1+” on the left*
“What about that?”
*quickly* “Nine!”
“How’d you know it was nine so fast?”
“You just added one more”
“So you didn’t need to recount because you remembered there were eight!
Dynamic Programming is just a fancy way to say ‘remembering stuff to save time later'”

特点

重叠子问题：动态规划适用于问题有重叠子问题的情况，即在求解过程中，相同的子问题会被多次求解。
最优子结构：问题的最优解包含其子问题的最优解。这意味着可以通过组合子问题的最优解来构造整个问题的最优解。
无后效性：一旦某个状态确定，它就不再改变，即后续的决策只依赖于这个状态和之后的决策，而与之前的决策无关。

基本步骤

定义状态：确定问题的状态，以及每个状态代表的意义。
状态转移方程：找出不同状态之间的转移关系，这是动态规划的核心，通常表现为递推式或递归式。
初始状态和边界情况：定义初始状态的值以及边界情况的处理，这是正确求解问题的基础。
计算顺序：确定状态的计算顺序，可以是自底向上（逐步构建小问题的解，直到解决整个问题），也可以是自顶向下（从整体问题出发，递归求解子问题，通常配合记忆化以避免重复计算）。
构建最终解：根据定义的状态和计算出的值，构建出整个问题的解。