如何深入理解Python中动态规划的算法思想集结？

本文共计4390个文字，预计阅读时间需要18分钟。

目录

1.概述

- 什么是堆叠子问题 - 动态规划与分治算法的区别 - 什么是最优子结构

2.流程

2.1 是否存在子问题 2.2 是否存在堆叠子问题 - 如何解决堆叠子问题 2.3 状态转移

3.总结

- 概述 - 动态规划

目录

• 1. 概述
• 什么是重叠子问题
• 动态规划与分治算法的区别
• 什么最优子结构
• 2. 流程
• 2.1 是否存在子问题
• 2.2 是否存在重叠子问题
• 怎么解决重叠子问题
• 2.3 状态转移
• 3.总结

1. 概述

动态规划算法应用非常之广泛。

对于算法学习者而言，不跨过动态规划这道门，不算真正了解算法。

初接触动态规划者，理解其思想精髓会存在一定的难度，本文将通过一个案例，抽丝剥茧般和大家聊聊动态规划。

动态规划算法有 3 个重要的概念：

• 重叠子问题。
• 最优子结构。
• 状态转移。

只有吃透这 3 个概念，才叫真正理解什么是动态规划。