Python在数据分析领域应用广泛吗？

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

1.+ 概述+ 动态规划算法应用非常广泛。对于算法学习者而言，不跨越动态规划这道门槛，不算真正懂算法。初接触动态规划者，理解其思想精髓会存在一定难度，本文将通过一个案例阐述。

1. 概述

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

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

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

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

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

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

什么是重叠子问题？

动态规划和分治算法有一个相似之处。

将原问题分解成相似的子问题，在求解的过程中通过子问题的解求出原问题的解。

动态规划与分治算法的区别：

• 分治算法的每一个子问题具有完全独立性，只会被计算一次。

  二分查找是典型的分治算法实现，其子问题是把数列缩小后再二分查找，每一个子问题只会被计算一次。

• 动态规划经分解得到的子问题往往不是互相独立的，有些子问题会被重复计算多次，这便是重叠子问题。

• 同一个子问题被计算多次，完全是没有必要的，可以缓存已经计算过的子问题，再次需要子问题结果时只需要从缓存中获取便可。这便是动态规划中的典型操作，优化重叠子问题，通过空间换时间的优化手段提高性能。

重叠子问题并不是动态规划的专利，重叠子问题是一个很普见的现象。

什么最优子结构？

最优子结构是动态规划的必要条件。