Python 动态规划

动态规划是一种解决多阶段决策过程中优化问题的方法，通常用于求解最优解问题，它采用递归的思想，将问题拆分成更小的子问题，并保存每个子问题的解，避免了重复计算，减少了时间复杂度。

在 Python 中实现动态规划算法，可以使用递归、记忆化搜索和动态规划三种方式，其中最常用的是动态规划方式。

动态规划的方式是先解决小问题，再逐步求解大问题，因此需要定义状态和状态转移方程，其中状态是描述问题子集的变量，状态转移方程是从已知状态推导出未知状态的方程。

以斐波那契数列为例，斐波那契数列定义为每个数是前两个数的和，即：

F[0] = 0

F[1] = 1

F[n] = F[n-1] + F[n-2] (n>=2)

可以使用动态规划方式求解斐波那契数列，首先定义状态为：

dp[n] 表示斐波那契数列第 n 个数的值。

然后定义状态转移方程为：

dp[0] = 0

dp[1] = 1

dp[n] = dp[n-1] + dp[n-2] (n>=2)

最后，使用循环方式求解 dp[n] 的值，代码如下：

def fib(n: int) -> int:
    dp = [0] * (n+1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

这样就可以用动态规划方式高效地求解斐波那契数列了。