【带你了解动态规划】-Toy模板网

这篇具有很好参考价值的文章主要介绍了【带你了解动态规划】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【带你了解动态规划】,动态规划

🔥博主：程序员不想YY啊🔥
💫CSDN优质创作者，CSDN实力新星，CSDN博客专家💫
🤗点赞🎈收藏⭐再看💫养成习惯
🌈希望本文对您有所裨益，如有不足之处，欢迎在评论区提出指正，让我们共同学习、交流进步！🌈

✨前言

动态规划是一种算法思想，主要用于求解具有重叠子问题和最优子结构性质的问题。在这类问题中，通过合理地保存子问题的解而避免重复计算，动态规划能够显著提高计算效率。动态规划通常用于解决最优化问题，诸如最短路径、最长公共子序列和背包问题等。

✨核心概念

👉最优子结构： 问题的最优解包含其子问题的最优解。简单来说，大问题的最优解可以由小问题的最优解组成。
👉重叠子问题： 在求解过程中，同一个子问题会被多次求解。这与分治算法的子问题不重合形成对比。
👉状态： 用于描述问题解法的一个情形，状态的精准定义对应不同的问题能有不同的形式。
👉转移方程（状态转移方程）： 定义了状态之间的关系，即如何从一个或多个较小的子问题的解得到当前问题的解。
👉边界条件： 这是动态规划中的基准情况，用以定义最小子问题的解。

✨ 解题步骤

👉定义状态： 第一步通常是定义状态，也就是找出问题的解可以被如何表述，并由此决定那些子问题需要被解决。
👉找出状态转移方程： 一旦状态被定义，下一步就是找出状态转移方程，用于描述状态之间是如何相互转换的。
👉确定边界条件： 确定初始条件或基准情况，这是动态规划的出发点。
👉计算顺序： 确定计算状态的顺序，有的问题需要正向计算，即从小状态到大状态，有的则需要反向计算。
👉实施计算/记忆化： 实施计算，可以采用自底向上（迭代）的方式，也可以自顶向下（递归+记忆化）。
👉构造解： 最后一步是通过保存的状态信息构造最终解答。

✨实例

让我们通过经典的斐波那契数列 (Fibonacci sequence) 作为动态规划的示例。

斐波那契数列问题中：

👉F(0) = 0
👉F(1) = 1
👉对于 n > 1, F(n) = F(n-1) + F(n-2)

👉状态： F(n)

👉状态转移方程： F(n) = F(n-1) + F(n-2)

👉边界条件： F(0) = 0, F(1) = 1

👉计算顺序： 自底向上，从2计算到n。

def fib(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for i in range(2, n+1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    return current

# 示例
print(fib(10))  # 输出第10个斐波那契数