前言

有些问题迟早要去面对。

一、动态规划的定义

动态规划：把一个待求解的问题划分成若干个子问题，先把各个子问题求解得出，再得出原问题的答案。对于多次出现的子问题，只求解一次，把答案保存起来，方便后续直接调用。（对于一些需要重复求解子问题的题目有很好的效果）

二、动态规划的适用情况（即被求解问题具有的性质）

2-1、最优子结构

最优子结构：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质。

2-2、子问题重叠

子问题重叠：即被求解问题在采用递归算法自顶向下求解时，每次产生的子问题并不总是新问题，有许多重复的子问题。这样采用动态规划就可以把多次出现的子问题只求解一次，把答案保存起来，方便后续调用。

2-3、无后效性

无后效性：即被求解问题的子问题的解是确定的，不会受到其他子问题的影响。

三、动态规划应用（斐波那契数列）

斐波那契数列：1，1，2，3，5，8……

求解斐波那契数列的第n项？

3-1、采用传统递归方法

# 使用传统方法，递归调用。
def fb(n):
    if n < 3: return 1
    else: return fb(n-1)+fb(n-2)
# n的值越大，则求解速度越慢，这是因为递归要求解大量的重复子问题。
# 自顶向下解决问题

3-2、使用动态规划思想

# 使用列表生成式生成全为1的列表。
x= [1 for i in range(50)]
# 使用动态规划方法。
def dp(n):
    i=2
    while i<n:
        x[i]=x[i-1]+x[i-2]
        i+=1
    # 列表下标从0开始，所以要减1.
    return x[i-1]
# 自底向上解决问题，每个子问题都会记录在列表中，

四、动态规划解决问题的步骤

参考链接：

动态规划的思想.

动态规划基本思想.

总结

提示：这里对文章进行总结：

例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。