动态规划（Dynamic Programming，简称 DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划的核心思想是，将问题分解成若干个子问题，通过求解子问题并将子问题的解存储起来，以便在需要时可以重复使用，从而避免了重复计算，提高了算法的效率。动态规划适用于有重叠子问题的问题，例如最短路径问题、背包问题、序列比对等。
动态规划的基本步骤包括：
- 确定状态：将原问题分解为若干个子问题，并用变量表示这些子问题的状态。
- 确定状态转移方程：建立状态之间的转移关系，即确定如何从一个状态转移到另一个状态。
- 确定边界条件：确定问题的最小子问题的解，也就是问题的初始状态和最终状态。
- 确定计算顺序：通常是从小的子问题开始计算，逐步推导出大问题的解。
动态规划有自顶向下和自底向上两种实现方式，其中自顶向下方法通常采用递归，自底向上方法通常采用迭代。动态规划在计算机科学中有很多应用，如最短路径算法、背包算法、序列比对等。下面是一个简单的动态规划 Demo，使用 Python 语言实现，基于斐波那契数列问题进行演示：
def fibonacci(n):
if n<=1:
return n
else:
fib_memo = [0]*(n+1)
fib_memo[1] = 1
for i in range(2, n+1):
fib_memo[i] = fib_memo[i-1] + fib_memo[i-2]
return fib_memo[n]
测试
n = 10
print(fibonacci(n))
输出：55
CopyCopy
在这个示例中，我们使用动态规划的方法求解斐波那契数列的第 n 项。我们首先定义了状态转移方程，然后通过迭代的方式计算出斐波那契数列的值。
