Python数据结构与算法（5）——动态规划

0. 学习目标

动态规划 (Dynamic Programming, DP) 是解决最优化问题的一种重要方法，它通过将原问题分解为相对简单的子问题的方式来求解复杂问题。动态规划在计算机科学、运筹学、经济学等领域有着广泛的应用。
通过本节学习，应掌握以下内容：

• 动态规划的基本概念和核心思想
• 动态规划的适用条件
• 动态规划的基本步骤和实现方法
• 典型动态规划问题的分析与解决

1. 动态规划的基本概念

1.1 什么是动态规划

动态规划是一种数学优化方法和算法范式，用于通过将复杂问题分解为更简单的子问题，并利用子问题的最优解来构造原问题的最优解​。在计算机科学中，如果问题满足最优子结构 (Optimal Substructure) 和重叠子问题 (Overlapping Subproblems) 两大属性，则可采用动态规划进行求解​。

1.2 动态规划的核心思想

动态规划基于以下两个核心思想：

• 最优子结构：整体问题的最优解可以由各子问题的最优解组合而成。当子问题的最优解能够以某种方式拼合出原问题的最优解时，称该问题具有最优子结构