算法介绍
- 动态规划（Dynamic Programming，DP），通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。它的关键思想是对于最终结果依赖前序步骤的问题，将结果定义为状态值dp，然后推导出后续步骤由前序步骤表达的状态转移方程，进而逐步计算求得最终结果。
经典问题：打家劫舍
-
LEETCODE第198题，打家劫舍，问题如下：
-
该问题与普通问题不一样的地方在于，偷了房间1就会导致不能偷房间2，而房间2中金额可能更多，导致不是最优结果。也有可能房间1金额不多但是房间3金额多，因此偷了房间2就不能偷房间3导致也不是最优结果。
-
这样思考的话，问题就会比较混乱，无法解。
-
因此，我们使用动态规划的思想，思考问题如下：
算法总结
- 通过以上例子，我们可以发现动态规划的核心在于建立用于评判好坏的dp指标和其随自变量的状态转移方程。
- 算法的基本原理如下：
- 最优子结构：一个问题的最优解包含了其子问题的最优解。
- 重叠子问题：在解决问题的过程中，子问题的解会被重复计算多次。
- 状态转移方程：描述了状态之间的关系，是动态规划的核心，用于从子问题的解推导出原问题的解。
- 边界条件：通常是最小子问题的解，是递推的基础。
- 算法的具体步骤为：
- 定义状态：确定动态规划的状态，即问题的变量表示。
- 状态转移：建立状态转移方程，描述如何从一个状态转移到另一个状态。
- 初始化：确定初始条件，通常是基础情况的解。
- 计算顺序：确定计算状态的顺序，通常是从底向上或从左到右。
- 求解：根据状态转移方程和初始条件，计算出所有状态的值，最终得到问题的解。
算法的应用：
各种优化问题：
- 最短路径问题：如Dijkstra算法和Floyd-Warshall算法。
- 背包问题：给定一组物品，每个物品有重量和价值，确定在不超过背包容量的情况下能够装入的最大价值。
- 编辑距离：计算将一个字符串转换为另一个字符串所需的最少操作次数（插入、删除、替换）。
- 旅行商问题（TSP）：寻找访问每个城市一次并返回原点的最短可能路线。
决策问题：
在决策过程中，动态规划可以帮助做出最优决策，如：
- 资源分配：在有限的资源下，如何分配资源以获得最大收益。
- 库存控制：决定何时以及多少库存以最小化成本。
- 序列决策：在多阶段决策过程中，每一步都以前一步的结果为基础，如马尔可夫决策过程（MDP）。
