子问题，递归，递推，分治，动态规划

我认为标题中的几个名词是有千丝万缕的联系，而且作为一名计算机科学的学习者，特别是算法领域， 深刻的理解这些名词背后的思想， 是非常重要的。

将原始问题拆解成子问题的方式，这在计算机领域是非常重要的一种解决问题的方式。 因为计算机非常的擅长解决重复的问题。 所以如果一个问题可以被划分成子问题， 通过迭代子问题， 即可求解原问题， 这也正是计算机所擅长的。

看看那些经典的算法： 二分查找，二叉搜索树查找，归并排序，快速排序，分治， 动态规划，深度优先搜索， 都是通过原始问题拆分成子问题的方式求解。

递归作为计算机语言的一种基本而又非常重要的编程范式，掌握它是非常重要的。 面对重复的问题，它可以优雅而又简洁求解重复的问题。 它可以解决最典型的问题就是： 递推式。记得在大一的时候， c语言书本上第一次介绍了递归，通过汉诺塔的例子来介绍的。 解决汉诺塔问题的核心思想就在于： 将规模为n的问题拆解为规模为n-1的问题，然后推导出递推式。 递归可以是一种编程手段，可以非常快捷的实现递推式。

斐波那契数列

最典型和简单的递推式就是斐波那契数列， 在面试题目中，它可是榜上有名的，它也通常是动态规划算法入门的经典例子。

斐波那契数列是非常有意思的一个递推式。 很多问题都可以直接转化成斐波那契数列： 如下几个问题，都可以转化成斐波那契数列

1.青蛙跳台阶的问题：有n台阶，每次青蛙可以选择跳1个台阶或者2个台阶，求爬阶梯的方式数

2.找零问题：一个商店只有1元和2元硬币，对于n元，有多少种找零方法？

3.一对刚出生的兔子(一公一母)被放到岛上，每对兔子出生两个月之后才开始繁殖后代。在兔子出生两个月后，每对兔子在每个月都将繁殖一对新的兔子。假定兔子不会死去，找出n个月后岛上兔子的对数

以上三个问题，都可以直接转化成斐波那契数列解决。

经典算法

下面再看看一些经典的算法， 它们是如何用子问题的方式去设计算法的。

分治

先看看分治相关的算法：

最经典是二分查找算和二叉搜索树的查找， 当然还有合并排序算法和快速排序算法， 它们的基本思想都是分而治之， 先将一个问题拆解成两个子问题，再将求解后的子问题转化成原问题。

对于分治算法来说， 1分为2是最经典的，当然还可以1分为3， 甚至1分为4， 当然如何划分， 这个看子问题怎么定义。

动态规划

再看看经典的动态规划算法：

这是一类算法思想， 有着非常广泛的应用场景。 如果一个问题可以划分成子问题， 那么就得考虑可能可以用动态规划思想。 上面已经提到了， 动态规划的最大的特点之一就是： 存在重叠子问题。 既然动态规划最基本的思想之一是通过子问题求解， 那么动态规划可以采用递归来实现， 并且在每次递归的过程中， 把已经求解的子问题记忆下来， 这样就不需要重复的求解子问题了。

下面列出几个比较典型的动态规划的问题：

1.一个字符串的最长递增子序列

2.两个字符串的最长公共子串

3.最经典的背包问题：给定n个重量为w1,w2...wn，价值为v1, v2...vn的物品和一个承重量为W的背包，求这些物品中最有价值的一个子集，并且能够装到背包中。

4.硬币找零问题：现有硬币1元，2元，5元(假设每种硬币的数量有无穷个)，对于n元找零的方式有多少？

既然动态规划是用于划分子问题的。 那么对于动态规划来说，划分子问题的方式有多少种呢。 在刘汝佳和黄亮的《算法艺术与信息学竞赛》这本书中，我认为归纳的非常好：

根据原问题所依赖的子问题的数目，和子问题所依赖的其它子问题的数目， 将动态规划方程式分类为四种。

具体可以参考-《算法艺术与信息学竞赛》——刘汝佳，黄亮

总结 

通过子问题的方式去求解问题，这是一种求解问题的基本思想之一。 由于原始问题可能比较复杂或者无序， 通过排列组合的方式将原始问题拆分成子问题， 让问题变得更加清晰和简单。 所以，通过子问题的方式， 是解决问题的一种通用的思想， 在不同的算法场景，有不同的应用。

而计算机天然的非常适合解决重复的问题。 而递归作为一种基本和非常重要的编程范式，可以非常优雅和简洁的写出代码。

所有的递推式都可以基于计算机的递归进行实现。

分治和动态规划是解决子问题的重要算法形式，当然区分这两个算法的特征就是： 是否有重叠子问题。 对于部分子问题， 分治和动态规划无法解决， 这时候就可以采用搜索算法， 基本上所有的问题都可以采用搜索来解决， 它是一种更为通用的算法了。

学习资料推荐

我认为在学习计算机的过程中，深入的理解这些概念是非常重要的，特别是在算法设计领域， 如果深刻的掌握这些概念， 学习起来会事倍功半。 下面我会介绍一些基本的学习资料：

我觉得可以从最基本的递归和递推开始学习：

关于递推式，推荐一本书:《离散数学及其应用》-Keneth H. Rosen， 可以重点关注 第八章-高级计数技术， 最好把相关的习题刷一遍， 并且编程实现递推式。

关于分治和动态规划，这部分书籍其实是比较多的，我先推荐一本比较基础的：《算法设计与分析基础》——Anany Levitin。 先把该书经典的题目过一遍。 纸上谈兵终觉浅， 建议在学习的过程中， 要加强实践， 推荐一个比较好的做题网站LeetCode。

动态规划的高阶进阶者，推荐一本神书： 《算法艺术与信息学竞赛》， 这本书的题目非常有意思，并且难度都不低。 如果能吃透了， 离传说中的大神就不远了。

最后： 对于学习计算机来说，唯一的捷径就是：一定要编程编程编程，然后总结总结总结！