当我们在谈论动态规划时，在谈些什么？

初次接触动态规划时在算法课

知其然，知其所以然 动态规划的发明历程

动态规划既是一种数学优化方法，也是一种计算机编程方法。该方法由Richard Bellman在 1950 年代开发，当时美国数学家Richard Bellman在研究多阶段决策过程的最优解时，提出了最优性原则，并将其应用到动态规划方法中。Bellman在其著作《动态规划》中详细介绍了这种方法，并且这本书的出版标志着动态规划作为一种数学方法的诞生。

动态规划最初的应用是在经济学中，用于解决投资和资源分配的问题。之后，动态规划方法被广泛地应用于许多其他领域，包括工程学、计算机科学、生物学和物理学等。特别是在计算机科学中，动态规划方法被广泛应用于算法设计和优化，如在图形处理、字符串匹配和最短路径等方面。

动态规划方法的本质是将大问题划分为若干个小问题，并将其按顺序求解。在求解每个小问题时，动态规划方法会保存已经解决的子问题的结果，以便后续计算时重复利用，避免重复计算，提高算法效率。因此，动态规划是一种非常强大的优化方法，能够解决很多复杂问题。

最优性原则是由Richard Bellman开发的动态规划的基本原则：最优路径具有以下特性：无论初始条件和初始阶段的控制变量（选择）如何，选择的控制（或决策变量）在剩下的时间段内，对于剩余的问题必须是最佳的，因为早期决定所导致的状态是最初的状况。

在编程中

以背包问题为例：

1. 定义状态：将问题抽象为状态。在背包问题中，状态可以定义为在前i个物品中选择一定物品放入一个容量为j的背包可以获得的最大价值。这里的i和j都是状态的变量。
2. 定义状态转移方程：确定状态转移的方式和公式。在背包问题中，状态转移方程可以定义为：当选择第i个物品时，背包剩余的容量为j，此时背包可以装下的最大价值为f(i, j) = max{f(i-1, j), f(i-1, j-w(i))+v(i)}。其中w(i)和v(i)分别表示第i个物品的重量和价值。
3. 确定边界条件：确定状态的起点和终点。在背包问题中，边界条件可以定义为：当i=0或j=0时，背包中的最大价值为0。
4. 计算最终结果：根据状态转移方程和边界条件，通过迭代计算得到最终的结果。在背包问题中，最终的结果为f(n, C)，其中n表示物品的总数，C表示背包的容量。

总的来说，动态规划是一种通过将问题拆分为多个子问题并重复利用已经计算出来的结果来求解最优解的方法。它在计算机编程和数学优化中都有着广泛的应用，并为我们提供了一种强大的工具来解决复杂的问题。