###################################
"""

将大规模的问题划分为可解决的小规模的问题；
类似思想的算法有：递归，分治算法

动态规划的使用场景：

1。求最大值，最小值
2。求是否存在一种方案
3。求一共有多少种方案（不需要关心具体的）


动态规划的常考题型：

1。 线性动态规划（一维数组）
2。 数组坐标处理（二维坐标处理）
3。 前缀字符串匹配和划分

背包问题：
    1）0-1背包问题
    2）完全背包问题
    3）多重背包问题


"""
###################################
'''
动态规划  vs 贪心算法

1。动态规划追求的是最终结果最优， 局部不一定最优
2。贪心算法追求的是局部最优， 不一定是最终的结果最优
3。贪心的算法（A*star, DFS 在某种情况都可以认为是一种贪心）

'''
###################################

"""
动态规划-四个要素
1。 处理状态
2。 化简问题的动态方程

3。 初始化
4。 最终结果

"""

###################################
"""
动态规划-四要素   ----vs---- 递归-四要素
1，处理状态 ------ 递归的定义
2。 动态规划公式 ----- 递归的拆解
3。 初始化  --------递归的出口
4。 动态规划的结果 ---- 递归的调用

动态规划可以是递归， 但动态规划不仅仅是递归
递归可以是动态规划，但不是所有的递归都是动态规划


"""

###################################
"""
动态规划的两种实现方式
1。 记忆搜索（递归来实现）
2。 迭代遍历（通常是for循环来实现）
3。 举例子： fibonacci数列
 
"""


################
"""
动态规划的 自顶向下   vs  自底向上

代码举例：
1。 fibonacci数列
2。 最长的自序列（数组里面最长的）
3。 杨辉三角
4。 公共最长自序列

"""