100种算法【Python版】第3篇——动态规划
找到事物发展的本质
- 1 动态规划原理
- 2 示例说明
-
- 2.1 上台阶问题
-
- 2.1.1 动态规划的思路
- 2.1.2 Python3代码
- 2.2 石子游戏
-
- 2.2.1 动态规划的思路
- 2.2.2 Python3代码
- 3 动态规划的应用
-
- 3.1 0-1背包问题
-
- 3.1.1 动态规划的思路
- 3.1.2 Python3代码
- 3.2 多重背包问题
-
- 3.2.1 动态规划思路
- 3.2.2 Python3代码
- 3.3 换零钱问题
-
- 3.3.1 动态规划思路
- 3.3.2 Python3代码
- 4 总结
-
- 4.1 优点
- 4.2 缺点
1 动态规划原理
动态规划（Dynamic Programming，简称 DP）是一种解决优化问题的算法设计技术，它通过状态定义和状态转移方程，将复杂问题拆解为简单的子问题，并通过存储中间结果来提高效率。它强调了通过组合已知状态来获得新状态的过程，适用于具有重叠子问题和最优子结构性质的问题。通过合理的设计状态和转移方程，可以高效地解决多种优化问题。
动态规划的原理：
（1）问题拆解
动态规划的基本思想是将一个复杂的问题拆解为多个较小的子问题。这些子问题通常是相似的，因此可以重复利用之前计算的结果。分治法分解的子问题是独立的，具有并行性；而动态规划分解的子问题具有连续性。
（2）状态定义
在动态规划中，首先需要定义“状态”。状态是对当前问题的一个具体描述，通常用一个或多个变量来表示。
（3）状态转移方程
状态转移方程是动态规划的核心，它描述了如何从一个或多个已知状态推导出当前状态的值。这个方程通常是基于问题的性质和结构来构建的，反映了选择和不选择的决策过程。
- 选择决策：对于每个子问题，可能存