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

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

1. 概述：动态规划+算法应用广泛。对算法学习者而言，动态规划是不可或缺的入门门径，但理解并非易事。初学者理解动态规划时，思维精髓的把握存在一定难度，本文将透过一个实例进行阐述。

1. 概述

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

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

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

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

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

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

什么是重叠子问题？

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

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

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

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

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

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